Problem Statement

You are given a simple directed acyclic graph G with N vertices numbered 1 to N. G has M edges, and the i-th edge is directed from vertex x_i to vertex y_i.

A permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) that satisfies the following condition is called a special permutation:

• P_{x_i} \lt P_{y_i} for all i=1,2,\cdots,M.

You are given a special permutation P. Takahashi and Aoki will play a game using it. Takahashi knows the value of each term of P, but Aoki only knows that P is a special permutation. Both of them know G. Takahashi selects some terms of P and tells Aoki their positions and values. Find the minimum number of terms that Takahashi needs to tell Aoki so that Aoki can determine the values of all terms of P.

Solve T test cases per input.

Constraints

• 1 \leq T \leq 10^4
• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq x_i,y_i \leq N
• The given graph G is a simple directed acyclic graph.
• 1 \leq P_i \leq N
• P_1,P_2,\ldots,P_N are pairwise distinct.
• P_{x_i} \lt P_{y_i}
• The sum of N over all test cases is at most 2 \times 10^5.
• The sum of M over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
3
6

In the first case, if Takahashi tells that P_1=5, \; P_4=2, Aoki can determine all terms of P. Also, if Takahashi tells only one term of P, Aoki cannot determine all terms of P.

Problem Statement

You are given integer sequences A=(A_1,A_2,\dots,A_N),\; B=(B_1,B_2,\dots,B_N) of length N consisting of 0 and 1. Let A[i,j] denote the contiguous subsequence from the i-th through j-th elements of sequence A. If i>j, A[i,j] is a sequence of length 0. You can perform the following operation on A at most \lfloor\frac{N}{2}\rfloor times:

• Choose four integers a,b,c,d that satisfy the following three conditions:
  • 1 \leq a \leq b < c \leq d \leq N
  • b-a=d-c
  • \sum_{i=a}^{b}{A_i}=\sum_{i=c}^{d}{A_i}
• Swap A[a,b] and A[c,d]. More precisely, replace A with the concatenation of A[1,a-1], A[c,d], A[b+1,c-1], A[a,b], A[d+1,N] in this order.

Determine whether it is possible to make A match B, and if possible, construct one sequence of operations.

Solve T test cases per input.

Constraints

• 1 \leq T \leq 25000
• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 1
• 0 \leq B_i \leq 1
• The sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

3
8
1 0 0 1 0 1 0 1
0 0 1 1 1 0 1 0
2
0 0
1 0
3
1 1 1
1 1 1

Sample Output 1

Yes
2
3 4 6 7
1 4 5 8
No
Yes
0

In the first test case, A is initially (1,0,0,1,0,1,0,1).
Performing the operation with (a,b,c,d)=(3,4,6,7) changes A to (1,0,1,0,0,0,1,1).
Then, performing the operation with (a,b,c,d)=(1,4,5,8) changes A to (0,0,1,1,1,0,1,0), which matches B.
In the second test case, it is impossible to make A match B.
In the third test case, A already matches B from the beginning.

Problem Statement

You are given a positive integer N.
Output one pair of non-negative integer sequences P=(P_1, P_2, \dots,P_N), A=(A_1, A_2, \dots,A_N) that satisfies all of the following conditions:

• 0 \leq P_i < 2^{30}~(1 \leq i \leq N)
• 0 \leq A_i < 2^{30}~(1 \leq i \leq N)
• The length of a longest strictly increasing subsequence of (P_1~\mathrm{OR}~A_i, P_2~\mathrm{OR}~A_i, \dots, P_N~\mathrm{OR}~A_i) is i. (1 \leq i \leq N)
  • \mathrm{OR} denotes the bitwise \mathrm{OR} operation.

It can be proved that under the constraints of this problem, there exists at least one pair P, A that satisfies the conditions.

Solve T test cases per input.

Constraints

• 1 \leq T
• 1 \leq N \leq 1024
• For test cases in a single input, the sum of N is at most 200000.
• For test cases in a single input, the sum of N^2 is at most 1024^2.
• All input values are integers.

Sample Input 1

3
3
8
1

Sample Output 1

3 14 5
13 2 10
6 902 909 186 684 219 471 248
1023 249 64 0 264 768 778 794
2025
1026

For the first test case, the sample output is P = (3, 14, 5), A = (13, 2, 10).

• One longest strictly increasing subsequence of (3~\mathrm{OR}~13, 14~\mathrm{OR}~13, 5~\mathrm{OR}~13) = (15, 15, 13) is (13), whose length is 1.
• One longest strictly increasing subsequence of (3~\mathrm{OR}~2, 14~\mathrm{OR}~2, 5~\mathrm{OR}~2) = (3, 14, 7) is (3, 7), whose length is 2.
• One longest strictly increasing subsequence of (3~\mathrm{OR}~10, 14~\mathrm{OR}~10, 5~\mathrm{OR}~10) = (11, 14, 15) is (11, 14, 15), whose length is 3.

From the above, it can be confirmed that P = (3, 14, 5), A = (13, 2, 10) satisfies the conditions.

Problem Statement

A sequence that can be obtained as A by performing the following operations is called a special sequence:

• Prepare an undirected graph consisting of N vertices and 0 edges, and a sequence A of length 0.
• Prepare queries for integers i,j satisfying 1 \leq i < j \leq N and q \in \{1,2\}:
• When q=1, connect vertices i and j with an edge.
• When q=2, append 1 to the end of A if vertices i and j are connected, and append 0 otherwise.
• There are N(N-1) possible queries; rearrange them in any order and process them in that order.

You are given a sequence B of length \frac{N(N-1)}{2} consisting of 0 and 1. You can perform the following operation on B any number of times:

• Choose an integer i satisfying 1 \leq i \leq \frac{N(N-1)}{2}-1, and swap B_i and B_{i+1}.

Determine whether it is possible to make B a special sequence, and if possible, find the minimum number of operations required.

Solve T test cases per input.

Constraints

• 1 \leq T
• 2 \leq N \leq 500
• |B| =\frac{N(N-1)}{2}
• 0 \leq B_i \leq 1
• The sum of |B| over all test cases is at most 3 \times 10^5.
• The sum of N^3 over all test cases is at most 500^3.
• All input values are integers.

Sample Input 1

4
4
1 1 0 1 1 0
2
1
3
0 0 0
5
1 1 1 1 1 1 1 1 1 0

Sample Output 1

1
0
0
3

In the first test case, if the queries are processed in the order (q,i,j)=(1,1,4), (2,1,4), (1,2,4), (2,1,2), (1,1,2), (2,2,3), (2,2,4), (2,3,4), (1,3,4), (1,1,3), (2,1,3), (1,2,3), the resulting sequence is (1,1,0,1,0,1), and B can be changed to this sequence by performing the operation once. Also, (1,1,0,1,1,0) is not a special sequence, so the answer is 1.

Problem Statement

For a string X = X_1X_2\dots X_{|X|} and positive integers l,r~(1 \leq l \leq r \leq |X|), let X_{l,r} = X_l X_{l+1}\dots X_r.

You are given a string S=S_1S_2\dots S_{|S|} consisting of A and B.
You are given Q queries. For each query, answer the following question:

• Starting from the state T = S_{l,r}, find the minimum possible length of a palindrome that can be obtained by performing the operation "choose one occurrence of AB that appears as a contiguous substring in T and delete it" zero or more times.
  If no palindrome can be obtained regardless of how the operation is performed, output -1.

Constraints

• 1 \leq |S| \leq 4 \times 10^5
• 1 \leq Q \leq 5 \times 10^4
• 1 \leq l \leq r \leq |S|
• S is a string consisting of A and B.
• Q,l,r are integers.

Sample Input 1

ABBABB
5
1 6
4 5
3 5
2 3
3 4

Sample Output 1

2
0
1
2
-1

For the first, second, and third queries, by performing the operation as follows, you can obtain a palindrome with the minimum length among those obtained by the operation.

• ABBABB \rightarrow ABBB \rightarrow BB
• AB \rightarrow (empty string)
• BAB \rightarrow B