Problem Statement

There is a rooted tree with N vertices. The vertices are numbered 1,2,\ldots,N, and the root is vertex 1. The parent of each vertex v (2 \leq v \leq N) is vertex P_v, where 1 \leq P_v < v.

Additionally, each vertex holds an integer sequence. Initially, the sequence held by vertex v is (v).

You will perform the following operation N-1 times.

• Choose a vertex v with 2 \leq v \leq N that has not been chosen in any previous operation, and let u be its parent in the current tree.
• Concatenate the sequence of vertex v to the end of the sequence of vertex u.
• Contract vertex v into its parent u. That is, delete vertex v and make all of its children into children of vertex u.

Find the number, modulo 998244353, of operation sequences such that the sequence of the remaining vertex 1 after all operations equals (1,2,\ldots,N). Here, two operation sequences are considered different if their sequences of chosen vertices are different.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 125000
• 2 \leq N \leq 250000
• 1 \leq P_v < v (2 \leq v \leq N)
• The sum of N over all test cases in a single input is at most 250000.
• All input values are integers.

Sample Input 1

6
4
1 2 1
5
1 1 3 3
2
1
5
1 2 3 4
4
1 1 1
8
1 1 2 4 2 6 3

Sample Output 1

2
6
1
24
1
24

In the first test case, if the vertices are chosen in the order 3,2,4, for example, the sequences change as follows.

• Choosing vertex 3 makes the sequence of vertex 2 equal to (2,3).
• Choosing vertex 2 makes the sequence of vertex 1 equal to (1,2,3).
• Choosing vertex 4 makes the sequence of vertex 1 equal to (1,2,3,4).

There are 2 orders of choosing vertices that satisfy the condition: (2,3,4) and (3,2,4).

Problem Statement

You are given integers N,M and M triples of integers (L_i,R_i,C_i). Here, 1 \leq L_i < R_i \leq N, and the pairs (L_i,R_i) are pairwise distinct.

Determine whether there exists a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) that satisfies all of the following M conditions. If one exists, find one such permutation.

• The i-th condition: the number of integers j such that L_i \leq j \leq R_i and \max(P_{L_i},P_{L_i+1},\ldots,P_j)=P_j is exactly C_i.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 125000
• 2 \leq N \leq 100
• 1 \leq M \leq \dfrac{N(N-1)}{2}
• 1 \leq L_i \lt R_i \leq N (1 \leq i \leq M)
• (L_i,R_i) \neq (L_j,R_j) (1 \leq i \lt j \leq M)
• 1 \leq C_i \leq R_i-L_i+1 (1 \leq i \leq M)
• The sum of N^3 over all test cases in a single input is at most 10^6.
• All input values are integers.

Sample Input 1

8
4 3
1 4 2
2 4 1
3 4 2
3 3
1 2 2
2 3 2
1 3 2
2 1
1 2 1
2 1
1 2 2
6 5
1 6 3
2 5 3
3 6 2
4 6 1
5 6 2
5 10
1 2 2
1 3 2
1 4 2
1 5 2
2 3 1
2 4 1
2 5 1
3 4 2
3 5 2
4 5 1
3 2
1 3 3
2 3 1
3 2
1 2 1
1 3 2

Sample Output 1

Yes
2 4 1 3
No
Yes
2 1
Yes
1 2
Yes
2 1 4 6 3 5
Yes
2 5 1 4 3
No
Yes
2 1 3

In the first test case, for example, P=(2,4,1,3) satisfies the conditions. The integers j counted in each condition are j=1,2 for the interval [1,4], j=2 for the interval [2,4], and j=3,4 for the interval [3,4].

In the second test case, the first two conditions require P_1 \lt P_2 \lt P_3. Then, the number of integers j counted for the interval [1,3] is 3, which violates the third condition, so no such permutation exists.

Problem Statement

You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N). Additionally, there is a queue that is initially empty.

You can perform the following three types of operations any number of times, in any order.

• Append operation: If P is not empty, remove the first element of P and add that element to the end of the queue.
• Output operation: If the queue is not empty, remove the front element and output its value.
• Reverse operation: Reverse the order of the elements in the queue. That is, if the elements of the queue are currently (v_1,v_2,\ldots,v_k), replace them with (v_k,v_{k-1},\ldots,v_1).

You want to output all elements so that the output values are 1,2,\ldots,N in this order.

Determine whether this is possible. If it is possible, find the minimum number of reverse operations required.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 250000
• 1 \leq N \leq 250000
• 1 \leq P_i \leq N (1 \leq i \leq N)
• P_1,P_2,\ldots,P_N are pairwise distinct.
• The sum of N over all test cases in a single input is at most 250000.
• All input values are integers.

Sample Input 1

10
4
3 2 4 1
5
2 4 3 5 1
1
1
4
1 2 3 4
5
5 4 3 2 1
8
2 1 4 3 6 5 8 7
2
2 1
1
1
9
2 8 3 5 6 7 1 9 4
3
2 3 1

Sample Output 1

3
-1
0
0
1
4
1
0
-1
2

In the first test case, for example, you can perform the operations as follows.

This performs the reverse operation 3 times. It cannot be achieved with 2 or fewer reverse operations, so the answer is 3.

Problem Statement

Consider the following decision problem X.

• You are given a simple undirected graph G with vertex set V=\{1,2,\ldots,N\} and a length-N sequence of positive integers D=(D_1,D_2,\ldots,D_N). Here, letting \deg_G(i) denote the degree of vertex i in G, the inequality D_i\leq \deg_G(i) holds for every vertex i. Also, \sum_{i=1}^N D_i is even.
• Determine whether it is possible to delete zero or more edges of G so that the degree of every vertex i becomes D_i. The answer is Possible if this can be done, and Impossible otherwise.

For S\subseteq V, define the following.

• e_G(S): The number of edges of G with both endpoints in S.
• e_G(i,S): The number of edges of G connecting vertex i\notin S to a vertex in S.

Snuke came up with the following conjecture Y about problem X.

The statement "for every subset S of V, \left(\sum_{i\in S}D_i\right)-2e_G(S)\leq \sum_{i\notin S}\min(D_i,e_G(i,S)) holds" is equivalent to the statement "the answer to problem X is Possible".

Intuitively, the condition says that "the number of edges that must leave S" must not exceed "the sum, over the vertices outside S, of the maximum number of edges that each of them can have toward S".

However, this conjecture is false.

You are given a length-N sequence of positive integers D, where \sum_{i=1}^N D_i is even. Determine whether there exists a simple undirected graph G with vertex set V satisfying D_i\leq\deg_G(i) for every vertex i such that (G,D) is a counterexample to conjecture Y.

You are given T test cases; solve each of them.

Constraints

• 1\leq T\leq 125000
• 2\leq N\leq 250000
• 1\leq D_i\leq N-1 (1\leq i\leq N)
• \sum_{i=1}^N D_i is even.
• The sum of N over all test cases in a single input is at most 250000.
• All input values are integers.

Sample Input 1

8
6
1 1 1 1 1 1
6
2 2 2 2 2 2
2
1 1
7
1 1 1 1 1 1 2
7
2 2 2 2 2 2 6
8
2 2 2 2 2 2 2 2
9
2 2 2 2 2 2 2 2 2
10
2 2 3 3 3 3 3 3 9 9

Sample Output 1

Yes
No
No
Yes
Yes
No
Yes
Yes

In the first test case, you can take G to be the graph consisting of a cycle on vertices 1,2,3 and a cycle on vertices 4,5,6. In this case, for example, for S=\{1,2,4\}:

• Left-hand side: \left(\sum_{i\in S}D_i\right)-2e_G(S) = (D_1+D_2+D_4)-2 \times 1 = 1
• Right-hand side: \sum_{i\notin S}\min(D_i,e_G(i,S)) = \min(D_3,2)+\min(D_5,1)+\min(D_6,1)=3

Thus, the inequality in conjecture Y holds. Similarly, the condition can be verified for every subset S.

On the other hand, no matter how the edges of G are deleted, it is impossible to make every vertex have degree 1. Therefore, this G is a counterexample, and the answer is Yes.