미친 가중치 배치

시간 제한2초메모리 제한1024 MB

요약

트리의 각 간선에 0 또는 1을 적어, 주어진 m개 경로의 XOR 값이 순서대로 비내림차순이 되도록 하는 경우의 수를 998244353으로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 9점
유형: 행렬, 비트 연산, 트리
정답자: 아직 제출이 없습니다

문제

조커는 트리를 가지고 있고, 그 트리에서 $m$ 개의 단순 경로 $(u_1, v_1)$ , $(u_2, v_2)$ , $\ldots$ , $(u_m, v_m)$ 을 골랐습니다. 각 경로는 양 끝 정점 $u_i$ 와 $v_i$ 로 주어지며, 모든 경로의 길이는 0이 아닙니다. 즉 $u_i \neq v_i$ 입니다.

조커는 트리의 각 간선에 정수 0 또는 1을 적으려 합니다. $s_i$ 를 $i$ 번째 경로 위 간선 가중치의 합을 2로 나눈 나머지로 정의합니다. 이 값은 그 경로에 있는 모든 간선 가중치의 XOR과 같습니다. 모든 $1 \le i < m$ 에 대해 $s_i \le s_{i+1}$ 이면 그 가중치 배치를 미친 배치라고 합니다.

미친 배치의 개수를 구하세요. 답은 998244353으로 나눈 나머지로 구합니다.

입력

첫 줄에 트리의 정점 수 $n$ 과 선택된 경로의 개수 $m$ 이 주어집니다 ( $2 \le n, m \le 250000$ ).

둘째 줄에는 $n-1$ 개의 정수 $p_i$ 가 주어집니다. 이는 정점 $p_i$ 와 정점 $i+1$ 을 잇는 간선이 있다는 뜻입니다 ( $1 \le p_i < i+1$ ).

이후 $m$ 개의 줄에는 $i$ 번째 경로의 양 끝 $u_i$ 와 $v_i$ 가 한 줄에 하나씩 주어집니다 ( $1 \le u_i < v_i \le n$ ).

출력

미친 배치의 개수를 998244353으로 나눈 나머지를 한 줄에 출력합니다.

예제3

예제 1
입력
```
3 3
1 2
1 2
2 3
1 3
```
예상 출력
```
2
```
예제 2
입력
```
4 4
1 1 1
1 2
2 3
3 4
1 4
```
예상 출력
```
3
```
예제 3
입력
```
4 2
1 2 3
1 2
3 4
```
예상 출력
```
6
```