406999: GYM102672 G Crazy arangements

Joker has a tree where he chose $$$m$$$ simple paths: $$$(u_1, v_1)$$$, $$$(u_2, v_2)$$$, $$$\ldots$$$, $$$(u_m, v_m)$$$ — each path is determined by two vertices $$$u_i$$$ and $$$v_i$$$, the start and the end. All paths have non-zero length, meaning $$$u_i \neq v_i$$$.

Now Joker intends to assign weights to edges — $$$0$$$ or $$$1$$$. Let's consider $$$s_i$$$ a sum of all weights of the edges along the $$$i$$$-th path modulo $$$2$$$ (in other words, xor of all weights along this path). Joker calls an arrangement of weights on the edges crazy, if the inequality is correct $$$s_{i} \le s_{i+1}$$$ for all $$$1 \le i < m$$$.

Your job  — calculate the number of crazy arrangements of weighs. Because Joker is crazy, he asked you to find the answer by modulo $$$998\,244\,353$$$.

The first line contains two integers $$$n$$$ and $$$m$$$ — the number of vertex in the tree and the number of chosen paths ($$$2 \le n, m \le 250\,000$$$).

The second line contains $$$n - 1$$$ integer $$$p_i$$$, denoting that there is an edge in the tree connecting the vertices $$$p_i$$$ and $$$i + 1$$$ ($$$1 \le p_i < i + 1$$$).

The next $$$m$$$ lines contain two integers each $$$u_i$$$ and $$$v_i$$$ — the start and the end of the $$$i$$$-th path ($$$1 \leq u_i < v_i \leq n$$$).

Output one number — the number of crazy arrangements of weights on the edges by modulo $$$998\,244\,353$$$.

3 3
1 2
1 2
2 3
1 3

2

4 4
1 1 1
1 2
2 3
3 4
1 4

3

4 2
1 2 3
1 2
3 4

6