CF2135C By the Assignment

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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

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$$$.

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

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$$$.