Problem Statement

There are N Reversi pieces arranged in a row. (A Reversi piece is a disc with a black side and a white side.) The state of each piece is represented by a string S of length N. If S_i=B, the i-th piece from the left is showing black; If S_i=W, the i-th piece from the left is showing white.

Consider performing the following operation:

• Choose i (1 \leq i < N) such that the i-th piece from the left is showing black and the (i+1)-th piece from the left is showing white, then flip both of those pieces. That is, the i-th piece from the left is now showing white and the (i+1)-th piece from the left is now showing black.

Find the maximum possible number of times this operation can be performed.

Constraints

• 1 \leq |S| \leq 2\times 10^5
• S_i=B or W

Sample Input 1

BBW

Sample Output 1

2

The operation can be performed twice, as follows:

• Flip the second and third pieces from the left.
• Flip the first and second pieces from the left.

Sample Input 2

BWBWBW

Sample Output 2

6

Problem Statement

Takahashi has N balls with positive integers written on them. The integer written on the i-th ball is A_i. He would like to form some number of pairs such that the sum of the integers written on each pair of balls is a power of 2. Note that a ball cannot belong to multiple pairs. Find the maximum possible number of pairs that can be formed.

Here, a positive integer is said to be a power of 2 when it can be written as 2^t using some non-negative integer t.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• A_i is an integer.

Sample Input 1

3
1 2 3

Sample Output 1

1

We can form one pair whose sum of the written numbers is 4 by pairing the first and third balls. Note that we cannot pair the second ball with itself.

Sample Input 2

5
3 11 14 5 13

Sample Output 2

2

Problem Statement

There are N strings arranged in a row. It is known that, for any two adjacent strings, the string to the left is lexicographically smaller than the string to the right. That is, S_1<S_2<...<S_N holds lexicographically, where S_i is the i-th string from the left.

At least how many different characters are contained in S_1,S_2,...,S_N, if the length of S_i is known to be A_i?

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• A_i is an integer.

Note

The strings do not necessarily consist of English alphabet; there can be arbitrarily many different characters (and the lexicographic order is defined for those characters).

Sample Input 1

3
3 2 1

Sample Output 1

2

The number of different characters contained in S_1,S_2,...,S_N would be 3 when, for example, S_1=abc, S_2=bb and S_3=c.

However, if we choose the strings properly, the number of different characters can be 2.

Sample Input 2

5
2 3 2 1 2

Sample Output 2

2

Problem Statement

Takahashi and Aoki will play a game using a grid with H rows and W columns of square cells. There are N obstacles on this grid; the i-th obstacle is at (X_i,Y_i). Here, we represent the cell at the i-th row and j-th column (1 \leq i \leq H, 1 \leq j \leq W) by (i,j). There is no obstacle at (1,1), and there is a piece placed there at (1,1).

Starting from Takahashi, he and Aoki alternately perform one of the following actions:

• Move the piece to an adjacent cell. Here, let the position of the piece be (x,y). Then Takahashi can only move the piece to (x+1,y), and Aoki can only move the piece to (x,y+1). If the destination cell does not exist or it is occupied by an obstacle, this action cannot be taken.
• Do not move the piece, and end his turn without affecting the grid.

The game ends when the piece does not move twice in a row.

Takahashi would like to perform as many actions (including not moving the piece) as possible before the game ends, while Aoki would like to perform as few actions as possible before the game ends. How many actions will Takahashi end up performing?

Constraints

• 1 \leq H,W \leq 2\times 10^5
• 0 \leq N \leq 2\times 10^5
• 1 \leq X_i \leq H
• 1 \leq Y_i \leq W
• If i \neq j, (X_i,Y_i) \neq (X_j,Y_j)
• (X_i,Y_i) \neq (1,1)
• X_i and Y_i are integers.

Sample Input 1

3 3 1
3 2

Sample Output 1

2

For example, the game proceeds as follows:

• Takahashi moves the piece to (2,1).
• Aoki does not move the piece.
• Takahashi moves the piece to (3,1).
• Aoki does not move the piece.
• Takahashi does not move the piece.

Takahashi performs three actions in this case, but if both players play optimally, Takahashi will perform only two actions before the game ends.

Sample Input 2

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

Sample Output 2

6

Sample Input 3

100000 100000 0

Sample Output 3

100000

Problem Statement

Takahashi's office has N rooms. Each room has an ID from 1 to N. There are also N-1 corridors, and the i-th corridor connects Room a_i and Room b_i. It is known that we can travel between any two rooms using only these corridors.

Takahashi has got lost in one of the rooms. Let this room be r. He decides to get back to his room, Room 1, by repeatedly traveling in the following manner:

• Travel to the room with the smallest ID among the rooms that are adjacent to the rooms already visited, but not visited yet.

Let c_r be the number of travels required to get back to Room 1. Find all of c_2,c_3,...,c_N. Note that, no matter how many corridors he passes through in a travel, it still counts as one travel.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq a_i,b_i \leq N
• a_i \neq b_i
• The graph given as input is a tree.

Sample Input 1

6
1 5
5 6
6 2
6 3
6 4

Sample Output 1

5 5 5 1 5

For example, if Takahashi was lost in Room 2, he will travel as follows:

• Travel to Room 6.
• Travel to Room 3.
• Travel to Room 4.
• Travel to Room 5.
• Travel to Room 1.

Sample Input 2

6
1 2
2 3
3 4
4 5
5 6

Sample Output 2

1 2 3 4 5

Sample Input 3

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

Sample Output 3

7 5 3 1 3 4 7 4 5

Problem Statement

You are given N-1 subsets of \{1,2,...,N\}. Let the i-th set be E_i.

Let us choose two distinct elements u_i and v_i from each set E_i, and consider a graph T with N vertices and N-1 edges, whose vertex set is \{1,2,..,N\} and whose edge set is (u_1,v_1),(u_2,v_2),...,(u_{N-1},v_{N-1}). Determine if T can be a tree by properly deciding u_i and v_i. If it can, additionally find one instance of (u_1,v_1),(u_2,v_2),...,(u_{N-1},v_{N-1}) such that T is actually a tree.

Constraints

• 2 \leq N \leq 10^5
• E_i is a subset of \{1,2,..,N\}.
• |E_i| \geq 2
• The sum of |E_i| is at most 2 \times 10^5.

Sample Input 1

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

Sample Output 1

1 2
1 3
3 4
4 5

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

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