G. Нули и единицы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дерево — это неориентированный связный граф без циклов.

Вам дано дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$. Каждой вершине $$$i$$$ ($$$1 \le i \le n$$$) сопоставлены начальное двоичное состояние $$$x_i$$$ ($$$x_i \in \{\texttt{0},\texttt{1}\}$$$) и целевое двоичное состояние $$$y_i$$$ ($$$y_i \in \{\texttt{0},\texttt{1}\}$$$).

Вы хотите сделать состояние каждой вершины равным её целевому состоянию. Для этого вы можете подавать энергетические импульсы в корневую вершину. Каждый раз, когда импульс подаётся в корень, он распространяется по дереву согласно следующим правилам:

  • Если текущее состояние вершины равно $$$\texttt{0}$$$, оно становится равным $$$\texttt{1}$$$, и импульс останавливается в этой вершине.

  • Иначе, если текущее состояние вершины равно $$$\texttt{1}$$$, оно становится равным $$$\texttt{0}$$$, и вершина отправляет по одному импульсу каждому из своих детей. Если у вершины нет детей, импульс исчезает. Каждый импульс, отправленный ребёнку, распространяется по тем же правилам.

Определите, можно ли сделать состояние каждой вершины равным её целевому состоянию. Если это возможно, найдите минимальное количество энергетических импульсов, необходимое для достижения этой цели. Поскольку это число может быть очень большим, выведите ответ по модулю $$$998\,244\,353$$$.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество вершин дерева.

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), обозначающих неориентированное ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что заданные рёбра образуют дерево.

Следующая строка содержит двоичную строку $$$x$$$ длины $$$n$$$, где $$$x_i$$$ ($$$1 \le i \le n$$$, $$$x_i \in \{\texttt{0},\texttt{1}\}$$$) обозначает начальное состояние вершины $$$i$$$.

Следующая строка содержит двоичную строку $$$y$$$ длины $$$n$$$, где $$$y_i$$$ ($$$1 \le i \le n$$$, $$$y_i \in \{\texttt{0},\texttt{1}\}$$$) обозначает целевое состояние вершины $$$i$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных, если невозможно сделать состояние каждой вершины равным её целевому состоянию, выведите $$$-1$$$. Иначе выведите минимальное необходимое количество энергетических импульсов по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
1
0
0
1
0
1
3
1 2
1 3
000
011
3
1 2
1 3
000
010
3
1 2
2 3
000
001
Выходные данные
0
1
2
-1
4
Примечание

В первом наборе входных данных начальные состояния уже совпадают с целевыми. Следовательно, энергетические импульсы не требуются, и ответ равен $$$0$$$.

Во втором наборе входных данных дерево состоит только из корня. Изначально его состояние равно $$$x_1 = \texttt{0}$$$.

После подачи одного импульса в корень его состояние становится равным $$$\texttt{1} = y_1$$$, и импульс останавливается. Следовательно, ответ равен $$$1$$$.

В третьем наборе входных данных необходимо $$$2$$$ импульса. На следующем изображении показано распространение обоих импульсов по дереву.

Распространение двух импульсов. После импульса $$$1$$$ состояния вершин становятся равны $$$\texttt{100}$$$, а импульс $$$2$$$ распространяется по дереву, позволяя достичь целевых состояний $$$\texttt{011}$$$.