C. По заданию
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для неориентированного связного графа из $$$n$$$ вершин, где $$$i$$$-я вершина имеет вес $$$v_i$$$, мы определяем значение простого пути$$$^{\text{∗}}$$$ $$$l_1, l_2, \ldots, l_m$$$ как $$$v_{l_1}\oplus v_{l_2}\oplus\cdots\oplus v_{l_m}$$$$$$^{\text{†}}$$$. Мы называем граф сбалансированным, если и только если:

  • Для каждого $$$1\le p \lt q\le n$$$ все простые пути от $$$p$$$ до $$$q$$$ имеют одинаковое значение.

Аквавейв предоставил вам неориентированный связный граф из $$$n$$$ вершин и $$$m$$$ рёбер, и $$$i$$$-я вершина в графе имеет вес $$$a_i$$$. Однако некоторые веса отсутствуют, что обозначается как $$$-1$$$.

Аквавейв хочет назначить целочисленный вес от $$$0$$$ до $$$V-1$$$ каждой вершине с $$$a_i=-1$$$, чтобы граф стал сбалансированным.

Вам нужно помочь Аквавейву найти количество способов назначить веса для достижения этой цели по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Простой путь от $$$c$$$ до $$$d$$$ — это последовательность вершин $$$l_1, l_2, \ldots, l_m$$$, где $$$l_1=c$$$, $$$l_m=d$$$, такая что между $$$l_i$$$ и $$$l_{i+1}$$$ есть ребро для каждого $$$1\le i\le m-1$$$, и нет повторяющихся вершин, т.е. $$$l_i\ne l_j$$$ для $$$1\le i \lt j\le n$$$.

$$$^{\text{†}}$$$$$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$V$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$n-1\le m\le \min\left(\frac{n(n-1)}{2}, 4\cdot 10^5\right)$$$, $$$1\le V\le 10^9$$$) — количество вершин, количество рёбер и верхняя граница весов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-1\le a_i\le V-1$$$) — веса вершин. $$$a_i=-1$$$ обозначает, что вес $$$i$$$-й вершины отсутствует.

Затем следуют $$$m$$$ строк, $$$i$$$-я строка содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1\le u,v\le n$$$) — две вершины, которые соединяет $$$i$$$-е ребро.

Гарантируется, что данный граф является простым и связным.

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

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

Для каждого набора входных данных выведите одно целое число — количество способов назначить веса, чтобы сделать граф сбалансированным, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
4 4 4
-1 -1 -1 -1
1 2
2 3
1 3
4 3
5 6 7
2 2 -1 2 2
1 2
1 3
1 4
2 5
3 5
4 5
7 8 9
-1 -1 -1 -1 0 -1 0
1 2
2 3
3 4
1 4
1 5
5 6
7 6
7 5
5 8 1000000000
1 2 3 4 -1
1 2
3 2
3 5
5 1
2 4
4 3
2 5
1 4
5 4 1000000000
-1 2 -1 3 -1
1 2
1 3
2 4
2 5
Выходные данные
4
1
9
0
747068572
Примечание

В первом наборе входных данных есть четыре возможных назначения:

  • $$$a=[0,0,0,0]$$$;
  • $$$a=[0,0,0,1]$$$;
  • $$$a=[0,0,0,2]$$$;
  • $$$a=[0,0,0,3]$$$.

Можно показать, что все эти назначения могут сделать граф сбалансированным.

Во втором наборе входных данных рассмотрим $$$(p,q)=(1,5)$$$. Простой путь $$$1\to 2\to 5$$$ имеет значение $$$2\oplus 2\oplus 2=2$$$, а простой путь $$$1\to 3\to 5$$$ имеет значение $$$2\oplus a_3\oplus 2=a_3$$$, так что единственное возможное значение для $$$a_3$$$ — это $$$2$$$. Можно показать, что $$$a_3=2$$$ может сделать граф сбалансированным.

В пятом наборе входных данных данный граф является деревом, поэтому существует только один простой путь между любыми двумя вершинами. Таким образом, мы можем назначить произвольное значение от $$$0$$$ до $$$V-1$$$ каждому $$$a_i$$$, и ответ равен $$$1\,000\,000\,000^3\bmod998\,244\,353=747\,068\,572$$$.