Problem Statement

We have N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

• 1 i j \colon Write the number i on a blank card and put it into box j.
• 2 i \colon Report all numbers written on the cards in box i, in ascending order.
• 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

• In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• For a query of the first kind:
  • 1 \leq i \leq 2 \times 10^5
  • 1 \leq j \leq N
• For a query of the second kind:
  • 1 \leq i \leq N
  • Box i contains some cards when this query is given.
• For a query of the third kind:
  • 1 \leq i \leq 2 \times 10^5
  • Some boxes contain a card with the number i when this query is given.
• At most 2 \times 10^5 numbers are to be reported.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write 1 on a card and put it into box 1.
• Write 2 on a card and put it into box 4.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1 and 2.
  • Print 1 and 2 in this order.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1, 1, and 2.
  • Note that you should print 1 twice.
• Boxes 1 and 4 contain a card with the number 1.
  • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
• Boxes 4 contains a card with the number 2.

Sample Input 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

Sample Output 2

1 2 200000
1

Problem Statement

Print all strictly increasing integer sequences of length N where all elements are between 1 and M (inclusive), in lexicographically ascending order.

Notes

For two integer sequences of the same length A_1,A_2,\dots,A_N and B_1,B_2,\dots,B_N, A is said to be lexicographically earlier than B if and only if:

• there is an integer i (1 \le i \le N) such that A_j=B_j for all integers j satisfying 1 \le j < i, and A_i < B_i.

An integer sequence A_1,A_2,\dots,A_N is said to be strictly increasing if and only if:

• A_i < A_{i+1} for all integers i (1 \le i \le N-1).

Constraints

• 1 \le N \le M \le 10
• All values in input are integers.

Sample Input 1

2 3

Sample Output 1

1 2 
1 3 
2 3 

The sought sequences are (1,2),(1,3),(2,3), which should be printed in lexicographically ascending order.

Sample Input 2

3 5

Sample Output 2

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

Problem Statement

The pattern of AtCoder's wallpaper can be represented on the xy-plane as follows:

• The plane is divided by the following three types of lines:
  • x = n (where n is an integer)
  • y = n (where n is an even number)
  • x + y = n (where n is an even number)
• Each region is painted black or white. Any two regions adjacent along one of these lines are painted in different colors.
• The region containing (0.5, 0.5) is painted black.

The following figure shows a part of the pattern.

You are given integers A, B, C, D. Consider a rectangle whose sides are parallel to the x- and y-axes, with its bottom-left vertex at (A, B) and its top-right vertex at (C, D). Calculate the area of the regions painted black inside this rectangle, and print twice that area.

It can be proved that the output value will be an integer.

Constraints

• -10^9 \leq A, B, C, D \leq 10^9
• A < C and B < D.
• All input values are integers.

Sample Input 1

0 0 3 3

Sample Output 1

10

We are to find the area of the black-painted region inside the following square:

The area is 5, so print twice that value: 10.

Sample Input 2

-1 -2 1 3

Sample Output 2

11

The area is 5.5, which is not an integer, but the output value is an integer.

Sample Input 3

-1000000000 -1000000000 1000000000 1000000000

Sample Output 3

4000000000000000000

This is the case with the largest rectangle, where the output still fits into a 64-bit signed integer.

Problem Statement

You are given a rooted tree with N vertices. The root is Vertex 1.
For each i = 1, 2, \ldots, N-1, the i-th edge connects Vertex u_i and Vertex v_i.

For each i = 1, 2, \ldots, N, let S_i denote the set of all vertices in the subtree rooted at Vertex i. (Each vertex is in the subtree rooted at itself, that is, i \in S_i.)

Additionally, for integers l and r, let [l, r] denote the set of all integers between l and r, that is, [l, r] = \lbrace l, l+1, l+2, \ldots, r \rbrace.

Consider a sequence of N pairs of integers \big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)\big) that satisfies the conditions below.

• 1 \leq L_i \leq R_i for every integer i such that 1 \leq i \leq N.
• The following holds for every pair of integers (i, j) such that 1 \leq i, j \leq N.
  • [L_i, R_i] \subseteq [L_j, R_j] if S_i \subseteq S_j
  • [L_i, R_i] \cap [L_j, R_j] = \emptyset if S_i \cap S_j = \emptyset

It can be shown that there is at least one sequence \big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)\big). Among those sequences, print one that minimizes \max \lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace, the maximum integer used. (If there are multiple such sequences, you may print any of them.)

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• All values in input are integers.
• The given graph is a tree.

Sample Input 1

3
2 1
3 1

Sample Output 1

1 2
2 2
1 1

(L_1, R_1) = (1, 2), (L_2, R_2) = (2, 2), (L_3, R_3) = (1, 1) satisfies the conditions.
Indeed, we have [L_2, R_2] \subseteq [L_1, R_1], [L_3, R_3] \subseteq [L_1, R_1], [L_2, R_2] \cap [L_3, R_3] = \emptyset.
Additionally, \max \lbrace L_1, L_2, L_3, R_1, R_2, R_3 \rbrace = 2 is the minimum possible value.

Sample Input 2

5
3 4
5 4
1 2
1 4

Sample Output 2

1 3
3 3
2 2
1 2
1 1

Sample Input 3

5
4 5
3 2
5 2
3 1

Sample Output 3

1 1
1 1
1 1
1 1
1 1

Problem Statement

You are given a tree T with N vertices. The vertices are numbered 1 to N, and the i-th edge (1 \leq i \leq N-1) connects vertices u_i and v_i bidirectionally.

Using T, define a complete graph G with N vertices as follows:

• The weight w(x,y) of the edge between vertices x and y in G is the shortest distance between vertices x and y in T.

Find one maximum weight maximum matching in G. That is, find a set of \lfloor N/2 \rfloor pairs of vertices M=\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\} such that each vertex 1,2,\dots, N appears in M at most once, and \displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i,y_i) is maximized.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq u_i < v_i \leq N
• The input graph is a tree.
• All input values are integers.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

2 4
1 3

In T, the distance between vertices 2 and 4 is 2, and the distance between vertices 1 and 3 is 2, so the weight of the matching \{(2,4),(1,3)\} is 4. There is no matching with a weight greater than 4, so this is a maximum weight maximum matching. Other acceptable outputs include:

2 3
1 4

Sample Input 2

3
1 2
2 3

Sample Output 2

1 3

In T, the distance between vertices 1 and 3 is 2, so the weight of the matching \{(1,3)\} is 2. There is no matching with a weight greater than 2, so this is a maximum weight maximum matching. Another acceptable output is:

3 1