Problem Statement

Let N be a positive odd number. A sequence of integers of length N, S = (S_1, S_2, \dots, S_N), is said to be M-type if "for each even number i = 2, 4, \dots, N - 1, it holds that S_{i-1} < S_i and S_i > S_{i+1}".

You are given a sequence of positive integers of length N, A = (A_1, A_2, \dots, A_N). Determine if it is possible to rearrange A to be M-type.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an odd number.
• 1 \leq A_i \leq 10^9 \ \ (1 \leq i \leq N)

Sample Input 1

5
1 2 3 4 5

Sample Output 1

Yes

The given sequence is A = (1, 2, 3, 4, 5). After rearranging it, for example, to B = (4, 5, 1, 3, 2),

• for i = 2, it holds that B_1 = 4 < 5 = B_2 and B_2 = 5 > 1 = B_3;
• for i = 4, it holds that B_3 = 1 < 3 = B_4 and B_4 = 3 > 2 = B_5.

Therefore, this sequence B is M-type, and the answer is Yes.

Sample Input 2

5
1 6 1 6 1

Sample Output 2

Yes

The given sequence A itself is M-type.

Sample Input 3

5
1 6 6 6 1

Sample Output 3

No

It is impossible to rearrange it to be M-type.

Problem Statement

For a positive integer X, let f(X) be the number of 1s that appear when X is represented in binary notation. For example, 6 = 110_{(2)}, \ 11 = 1011_{(2)}, \ 16 = 10000_{(2)}, so f(6) = 2, \ f(11) = 3, \ f(16) = 1.

You are given a positive integer N. Determine whether there is a positive integer X less than or equal to N such that f(X) = 3, and if so, find the maximum such X.

There are T test cases to solve.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^{18}

Sample Input 1

4
16
161
4
1000000000000000000

Sample Output 1

14
161
-1
936748722493063168

• For the first test case, f(14) = 3, \ f(15) = 4, \ f(16) = 1, so the maximum positive integer X satisfying X \leq 16 and f(X) = 3 is 14.
• For the second test case, f(161) = 3, so the maximum positive integer X satisfying X \leq 161 and f(X) = 3 is 161.
• For the third test case, f(1) = 1, \ f(2) = 1, \ f(3) = 2, \ f(4) = 1, so there is no positive integer X satisfying X \leq 4 and f(X) = 3.
• As seen in the fourth test case, the input and output values may not fit in a 32-bit integer type.

Problem Statement

You are given a tree with N vertices. The vertices are labeled from 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Moreover, for every vertex, the number of incident edges is odd.

You will color each vertex of the given tree either black ( B ) or white ( W ). Here, the string obtained by arranging the colors ( B or W ) of the vertices in the order of vertex labels is called a color sequence.

You are given a color sequence S. Determine whether the color sequence S can result from performing the following operation once when all vertices are colored, and if it can, find one possible color sequence before the operation.

Operation: For each vertex k = 1, 2, \dots, N, let C_k be the color that occupies the majority (more than half) of the colors of the vertices connected to k by an edge. For every vertex k, change its color to C_k simultaneously.

There are T test cases to solve.

Constraints

• T \geq 1
• N \geq 2
• The sum of N over the test cases in each input file is at most 2 \times 10^5.
• 1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq N - 1)
• The given edges (A_i, B_i) \ (1 \leq i \leq N - 1) form a tree.
• Each vertex k \ (1 \leq k \leq N) appears an odd number of times in total as A_i, B_i \ (1 \leq i \leq N - 1).
• S is a string of length N consisting of B and W.

Sample Input 1

2
4
1 2
1 3
1 4
BWWW
4
1 2
1 3
1 4
BBWW

Sample Output 1

WBBW
-1

For the first test case, suppose the color sequence before the operation was WBBW. In this case,

• for vertex 1, the colors of the connected vertices 2, 3, 4 are B, B, W, respectively, with C_1 = {}B occupying the majority;
• for vertex 2, the color of the connected vertex 1 is W, with C_2 = {}W occupying the majority;
• for vertex 3, the color of the connected vertex 1 is W, with C_3 = {}W occupying the majority;
• for vertex 4, the color of the connected vertex 1 is W, with C_4 = {}W occupying the majority.

Therefore, the color sequence after the operation is BWWW, satisfying the condition. Similarly, if the color sequence before the operation was WBBB, WBWB, or WWBB, the color sequence after the operation would be BWWW, and any of these are considered correct.

For the second test case, the color sequence BBWW cannot result from the operation on the given tree.

Problem Statement

We define the density of a non-empty simple undirected graph as \displaystyle\frac{(\text{number\ of\ edges})}{(\text{number\ of\ vertices})}.

You are given positive integers N and D. Determine whether there is a simple undirected graph G with N vertices and DN edges that satisfies the following condition. If it exists, find one such graph.

Condition: Let V be the vertex set of G. For any non-empty proper subset X of V, the density of the induced subgraph of G by X is strictly less than D.

Constraints

• N \geq 1
• D \geq 1
• DN \leq 5 \times 10^4

Sample Input 1

3 1

Sample Output 1

Yes
1 2
1 3
2 3

The printed graph has vertex set \{1, 2, 3\} and edge set \{(1, 2), (1, 3), (2, 3)\}, and is simple. The vertex set X has 6 non-empty proper subsets: \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}.

• For X = \{1\}, \{2\}, \{3\}, the edge sets of the induced subgraphs by X are empty, and the densities are \displaystyle\frac{0}{1} = 0.
• For X = \{1, 2\}, \{1, 3\}, \{2, 3\}, the edge sets of the induced subgraphs by X are \{(1, 2)\}, \{(1, 3)\}, \{(2, 3)\}, respectively, and the densities are all \displaystyle\frac{1}{2}.

In all cases, the density of the induced subgraph is strictly less than D = 1, so this graph satisfies the condition.

Sample Input 2

4 2

Sample Output 2

No

A simple undirected graph with 4 vertices and 8 edges does not exist.

Problem Statement

You are given a connected simple undirected graph with N vertices and \displaystyle\frac{3}{2}N edges, where N is a positive even number. The vertices are labeled from 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Moreover, for every vertex, the number of incident edges is exactly 3.

You will color each vertex of the given graph either black ( B ) or white ( W ). Here, the string obtained by arranging the colors ( B or W ) of the vertices in the order of vertex labels is called a color sequence.

Determine whether there is a color sequence that cannot result from performing the following operation once when all vertices are colored, and if there is such a color sequence, find one.

Operation: For each vertex k = 1, 2, \dots, N, let C_k be the color that occupies the majority (more than half) of the colors of the vertices connected to k by an edge. For every vertex k, change its color to C_k simultaneously.

There are T test cases to solve.

Constraints

• T \geq 1
• N \geq 4
• The sum of N over the test cases in each input file is at most 5 \times 10^4.
• N is an even number.
• 1 \leq A_i < B_i \leq N \ \ \left(1 \leq i \leq \displaystyle\frac{3}{2}N\right)
• (A_i, B_i) \neq (A_j, B_j) \ \ \left(1 \leq i < j \leq \displaystyle\frac{3}{2}N\right)
• The given graph is connected.
• Each vertex k \ (1 \leq k \leq N) appears exactly 3 times as A_i, B_i \ \left(1 \leq i \leq \displaystyle\frac{3}{2}N\right).

Sample Input 1

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

Sample Output 1

BWWW
BWWWBWWWBB

Let us consider the first test case. For the color of vertex 1 to be B, at least two of the colors of vertices 2, 3, 4 must be B before the operation. Then, for at least one of the vertices 2, 3, 4, at least two of the colors of the vertices connected to that vertex by an edge are B, so the color of that vertex after the operation will be B. Therefore, the color sequence BWWW cannot result from performing the operation.

Problem Statement

We define the density of a non-empty simple undirected graph as \displaystyle\frac{(\text{number\ of\ edges})}{(\text{number\ of\ vertices})}.

You are given positive integers N, D, and a simple undirected graph G with N vertices and DN edges. The vertices of G are numbered from 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Determine whether G satisfies the following condition.

Condition: Let V be the vertex set of G. For any non-empty proper subset X of V, the density of the induced subgraph of G by X is strictly less than D.

There are T test cases to solve.

Constraints

• T \geq 1
• N \geq 1
• D \geq 1
• The sum of DN over the test cases in each input file is at most 5 \times 10^4.
• 1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq DN)
• (A_i, B_i) \neq (A_j, B_j) \ \ (1 \leq i < j \leq DN)

Sample Input 1

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

Sample Output 1

Yes
No

• The first test case is the same as Sample Input 1 in Problem D, and it satisfies the condition.
• For the second test case, the edge set of the induced subgraph by the non-empty proper subset \{1, 2, 3\} of the vertex set \{1, 2, 3, 4\} is \{(1, 2), (1, 3), (2, 3)\}, and its density is \displaystyle\frac{3}{3} = 1 = D. Therefore, this graph does not satisfy the condition.