Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

• Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

• 1\leq N \leq 10^5
• 1 \leq A_j \leq N
• i occurs in A exactly three times, for each i=1,2,\dots,N.
• All input values are integers.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

• 1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
• 2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
• 3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3 4 1 2

Problem Statement

For a non-negative integer K, we define a level-K carpet as follows:

• A level-0 carpet is a 1 \times 1 grid consisting of a single black cell.
• For K > 0, a level-K carpet is a 3^K \times 3^K grid. When this grid is divided into nine 3^{K-1} \times 3^{K-1} blocks:
  • The central block consists entirely of white cells.
  • The other eight blocks are level-(K-1) carpets.

You are given a non-negative integer N.
Print a level-N carpet according to the specified format.

Constraints

• 0 \leq N \leq 6
• N is an integer.

Sample Input 1

1

Sample Output 1

###
#.#
###

A level-1 carpet is a 3 \times 3 grid as follows:

When output according to the specified format, it looks like the sample output.

Sample Input 2

2

Sample Output 2

#########
#.##.##.#
#########
###...###
#.#...#.#
###...###
#########
#.##.##.#
#########

A level-2 carpet is a 9 \times 9 grid.

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a (not necessarily contiguous) subsequence B=(B_1,B_2,\dots,B_M) of length M of A.

Notes

A subsequence of a number sequence is a sequence that is obtained by removing 0 or more elements from the original number sequence and concatenating the remaining elements without changing the order.

For example, (10,30) is a subsequence of (10,20,30), but (20,10) is not a subsequence of (10,20,30).

Constraints

• 1 \le M \le N \le 2000
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

21

When B=(A_1,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21. Since it is impossible to achieve 22 or a larger value, the solution is 21.

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

54

Problem Statement

There is a simple undirected graph with N vertices numbered 1 through N and M edges numbered 1 through M. Edge i connects vertex u_i and vertex v_i.
Every vertex is painted either red or blue. The color of vertex i is represented by C_i; vertex i is painted red if C_i is 0 and blue if C_i is 1.

Now, Takahashi is on vertex 1 and Aoki is on vertex N.
They may repeat the following move zero or more times.

• Each of the two simultaneously moves to a vertex adjacent to the current vertex.
  Here, the vertices that Takahashi and Aoki move to must have different colors.

By repeating the move above, can Takahashi and Aoki simultaneously end up on vertices N and 1, respectively?
If it is possible, find the minimum number of moves required. If it is impossible, print -1.

You are given T at the beginning of the input. Solve the problem for T test cases.

Constraints

• 1 \leq T \leq 1000
• 2 \leq N \leq 2000
• 1 \leq M \leq \min(\frac{N(N-1)}{2}, 2000)
• C_i \in \lbrace 0, 1 \rbrace
• 1 \leq u_i, v_i \leq N
• The graph given in the input is simple.
• All values in the input are integers.
• The sum of N over all test cases does not exceed 2000.
• The sum of M over all test cases does not exceed 2000.

Sample Input 1

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

Sample Output 1

3
-1
3

For the 1-st test case, Takahashi and Aoki can achieve the objective by making the following 3 moves, which is the minimum number:

• Takahashi moves to vertex 3, and Aoki moves to vertex 2.
• Takahashi moves to vertex 2, and Aoki moves to vertex 3.
• Takahashi moves to vertex 4, and Aoki moves to vertex 1.

Note that in the 1-st move, it is disallowed that both Takahashi and Aoki move to vertex 2 (because the colors of vertices that Takahashi and Aoki move to must be different.)

For the 2-nd case, no matter how they move, they cannot achieve the objective.

Problem Statement

You are given two sequences of N numbers: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

Takahashi can repeat the following operation any number of times (possibly zero).

Choose three pairwise distinct integers i, j, and k between 1 and N.
Swap the i-th and j-th elements of A, and swap the i-th and k-th elements of B.

If there is a way for Takahashi to repeat the operation to make A and B equal, print Yes; otherwise, print No.
Here, A and B are said to be equal when, for every 1\leq i\leq N, the i-th element of A and that of B are equal.

Constraints

• 3 \leq N \leq 2\times 10^5
• 1\leq A_i,B_i\leq N
• All values in the input are integers.

Sample Input 1

3
1 2 1
1 1 2

Sample Output 1

Yes

Performing the operation once with (i,j,k)=(1,2,3) swaps A_1 and A_2, and swaps B_1 and B_3,
making both A and B equal to (2,1,1). Thus, you should print Yes.

Sample Input 2

3
1 2 2
1 1 2

Sample Output 2

No

There is no way to perform the operation to make A and B equal, so you should print No.

Sample Input 3

5
1 2 3 2 1
3 2 2 1 1

Sample Output 3

Yes

Sample Input 4

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

Sample Output 4

No