C. By the Assignment
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

For an undirected connected graph of $$$n$$$ vertices, where the $$$i$$$-th vertex has a weight of $$$v_i$$$, we define the value of a simple path$$$^{\text{∗}}$$$ $$$l_1, l_2, \ldots, l_m$$$ as $$$v_{l_1}\oplus v_{l_2}\oplus\cdots\oplus v_{l_m}$$$$$$^{\text{†}}$$$. We call the graph balanced if and only if:

  • For every $$$1\le p \lt q\le n$$$, all simple paths from $$$p$$$ to $$$q$$$ have the same value.

Aquawave has given you an undirected connected graph of $$$n$$$ vertices and $$$m$$$ edges, and the $$$i$$$-th vertex in the graph has a weight of $$$a_i$$$. However, some of the weights are missing, represented by $$$-1$$$.

Aquawave wants to assign an integer weight between $$$0$$$ and $$$V-1$$$ to each vertex with $$$a_i=-1$$$, so that the graph will be balanced.

You have to help Aquawave find the number of ways to assign weights to achieve the goal, modulo $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$A simple path from $$$c$$$ to $$$d$$$ is a sequence of vertices $$$l_1, l_2, \ldots, l_m$$$, where $$$l_1=c$$$, $$$l_m=d$$$, such that there is an edge between $$$l_i$$$ and $$$l_{i+1}$$$ for every $$$1\le i\le m-1$$$, and there are no repeated vertices, i.e. $$$l_i\ne l_j$$$ for $$$1\le i \lt j\le n$$$.

$$$^{\text{†}}$$$$$$\oplus$$$ denotes the bitwise XOR operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$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$$$) — the number of vertices, the number of edges, and the upper bound of weights.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-1\le a_i\le V-1$$$) — the weights of the vertices. $$$a_i=-1$$$ represents that the weight of the $$$i$$$-th vertex is missing.

Then $$$m$$$ lines follow, the $$$i$$$-th line containing two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$) — the two vertices that the $$$i$$$-th edge connects.

It is guaranteed that the given graph is simple and connected.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$4\cdot 10^5$$$.

Output

For each test case, output a single integer — the number of ways to assign weights to make the graph balanced, modulo $$$998\,244\,353$$$.

Example
Input
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
Output
4
1
9
0
747068572
Note

In the first test case, there are four possible assignments:

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

It can be shown that all of these assignments can make the graph balanced.

In the second test case, we will pick $$$(p,q)=(1,5)$$$. The simple path $$$1\to 2\to 5$$$ has a value of $$$2\oplus 2\oplus 2=2$$$, and the simple path $$$1\to 3\to 5$$$ has a value of $$$2\oplus a_3\oplus 2=a_3$$$, so the only possible value for $$$a_3$$$ is $$$2$$$. It can be shown that $$$a_3=2$$$ can make the graph balanced.

In the fifth test case, the given graph is a tree, so there is only one simple path between any two vertices. Thus, we can assign an arbitrary value between $$$0$$$ and $$$V-1$$$ to each $$$a_i$$$, and the answer is $$$1\,000\,000\,000^3\bmod998\,244\,353=747\,068\,572$$$.