C. By the Assignmenttime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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<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<j\le n$$$. $$$^{\text{†}}$$$$$$\oplus$$$ denotes the bitwise XOR operation. InputEach 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$$$.OutputFor each test case, output a single integer — the number of ways to assign weights to make the graph balanced, modulo $$$998\,244\,353$$$.ExampleInput54 4 4-1 -1 -1 -11 22 31 34 35 6 72 2 -1 2 21 21 31 42 53 54 57 8 9-1 -1 -1 -1 0 -1 01 22 33 41 41 55 67 67 55 8 10000000001 2 3 4 -11 23 23 55 12 44 32 51 45 4 1000000000-1 2 -1 3 -11 21 32 42 5Output4
1
9
0
747068572
NoteIn 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$$$.