Problem Statement

There are N seats arranged in a row. Each seat can accommodate at most one person. Determine whether it is possible to seat M people in the seats satisfying the following condition.

No two adjacent seats may both be occupied.

Constraints

• 1 \le N, M \le 100
• All input values are integers.

Sample Input 1

6 3

Sample Output 1

Yes

For example, seating people in the first, third, and sixth seats from the left is one valid way. Thus, output Yes.

Sample Input 2

4 3

Sample Output 2

No

There is no valid way to seat the people satisfying the condition. Thus, output No.

Sample Input 3

5 3

Sample Output 3

Yes

Sample Input 4

44 7

Sample Output 4

Yes

Problem Statement

You are given a string S consisting of lowercase English letters. Remove all occurrences of the most frequent character(s) in S, then output the remaining characters concatenated in their original order.

If there are multiple characters with the maximum frequency, remove all of them.

Constraints

• 1 \le |S| \le 100
• S is a string consisting of lowercase English letters.

Sample Input 1

mississippi

Sample Output 1

mpp

The most frequent characters in mississippi are s and i, each appearing four times. Removing all occurrences of s and i yields the string mpp.

Sample Input 2

atcoder

Sample Output 2

Sample Input 3

beginner

Sample Output 3

bgir

Problem Statement

You are given strings S and T consisting of uppercase English letters.

You may perform the following two types of operations any number of times (possibly zero) in any order:

• Insert one character A at any position in S (possibly the beginning or the end).
• Choose one character A in S and delete it. The remaining characters are concatenated in their original order.

Determine whether it is possible to make S equal to T, and if so, find the minimum total number of operations required.

Constraints

• S and T are strings of uppercase English letters with length between 1 and 3\times 10^5, inclusive.

Sample Input 1

ABC
BACA

Sample Output 1

3

It is possible to make S equal to T in three operations in total, as follows:

• Insert one A between the second and third characters of S. Now, S= ABAC.
• Delete the first character of S, which is A. Now, S= BAC.
• Insert one A at the end of S. Now, S= BACA.

It is impossible to make S equal to T in two or fewer operations, so the answer is 3.

Sample Input 2

ABC
ARC

Sample Output 2

-1

No matter how operations are performed, it is impossible to make S equal to T.

Sample Input 3

ABC
ABC

Sample Output 3

0

No operations need to be performed.

Sample Input 4

AAAWAZAAAABAAAU
AWAAZABAAAAAUA

Sample Output 4

9

Problem Statement

You are given a string S consisting of the three characters A, B, and C.

Define an operation as follows:

Choose a tuple (i, j, k) satisfying 1 \le i \lt j \lt k \le |S|, S_i = A, S_j = B, and S_k = C, and remove the i-th, j-th, and k-th characters from S. The remaining characters are packed to the left in their original order.

Find the maximum number of times the operation can be performed on string S.

Constraints

• 1 \le |S| \le 10^{6}
• S is a string consisting of A, B, and C.

Sample Input 1

ABACBCC

Sample Output 1

2

The operation can be performed twice as follows:

• For ABACBCC, perform the operation with (i, j, k) = (1, 2, 7). The remaining string is ACBC.

• For ACBC, perform the operation with (i, j, k) = (1, 3, 4). The remaining string is C.

The operation cannot be performed three or more times, so the answer is 2. Thus, output 2.

Sample Input 2

CBACBB

Sample Output 2

0

Sample Input 3

BBBAAABCBCBAACBBCAAC

Sample Output 3

5

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges. Here, N \geq 2. The vertices are numbered 1 to N, and the edges are numbered 1 to M; edge i connects vertices U_i and V_i. Each edge has a value called a cost, and the cost of edge i is 2^i.

You will now choose some edges of G to delete so that the number of connected components of G becomes exactly 2. (It can be proved that this is always achievable under the constraints of this problem.)

Find the minimum possible sum of costs of the deleted edges, modulo 998244353. (Note that you are not minimizing the remainder modulo 998244353.)

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right)
• 1 \leq U_i < V_i \leq N
• (U_i, V_i) \neq (U_j, V_j) if i \neq j
• G is connected.
• All input values are integers.

Sample Input 1

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

Sample Output 1

22

Deleting edges 1, 2, 4 (the edges shown as dashed lines in the figure above) makes the number of connected components of G exactly 2.

In this case, the sum of costs of the deleted edges is 2^1+2^2+2^4=22, which is the minimum.

Sample Input 2

2 1
1 2

Sample Output 2

2

Sample Input 3

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

Sample Output 3

54

Problem Statement

You are given a tree T with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.

For a positive integer k, define a "centipede graph of length k" as a graph with 3k vertices obtained by the following procedure:

• Prepare a path graph with k vertices.
• For each vertex v of the path graph, add two new vertices adjacent only to v.

For example, a centipede graph of length 4 is as shown in the figure below.

Find the maximum x such that a "centipede graph of length x" is contained as a subgraph of tree T.

Q test cases are given; solve each of them.

Constraints

• 1 \le Q
• 3 \le N \le 2 \times 10^5
• 1 \le A_i, B_i \le N
• The given graph is a tree.
• 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 3
2 4
2 5
2 6
3 5
4 7
5 8
5
1 5
1 2
1 3
3 4
15
13 3
4 13
11 1
14 9
9 13
13 6
1 10
7 9
13 2
10 5
3 12
15 13
9 10
12 8

Sample Output 1

2
1
3

For the first test case, the graph consisting of the six vertices 2,3,4,5,6,8 forms a "centipede graph of length 2".

No centipede graph of length 3 or more is contained as a subgraph, so the answer is 2. Thus, output 2.

Problem Statement

Snuke is choosing problems to use in programming contests he is hosting. Snuke has N problem candidates numbered 1 to N, where problem candidate i has difficulty i, genre K_i, and interest A_i.

Hoping to entertain participants of a wider range of skill levels, he plans to simultaneously hold two contests called Div. 1 and Div. 2, each featuring four problems chosen from the N problem candidates with pairwise distinct genres. However, to conserve problem candidates, the two easier problems in Div. 1 and the two harder problems in Div. 2 will be the same, so only six problems in total will be used.

More formally, the following holds:

• Snuke chooses six problem candidates from the N candidates. Let the numbers of the chosen problem candidates in ascending order be i_1, i_2, \dots, i_6.
• Problem candidates i_1, i_2, i_3, i_4 are used in Div. 2, and they must be of pairwise distinct genres. That is, K_{i_1}, K_{i_2}, K_{i_3}, K_{i_4} must be pairwise distinct.
• Problem candidates i_3, i_4, i_5, i_6 are used in Div. 1, and they must be of pairwise distinct genres. That is, K_{i_3}, K_{i_4}, K_{i_5}, K_{i_6} must be pairwise distinct.

Determine whether there exists a valid choice of six problems satisfying the conditions, and if so, find the maximum total interest of the six chosen problems.

Constraints

• 6 \leq N \leq 10^5
• 1 \leq K_i \leq N
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

32

For example, consider choosing problem candidates 1, 2, 3, 5, 6, 8. In this case, K_{i_1}=1, K_{i_2}=3, K_{i_3}=2, K_{i_4}=4 are pairwise distinct, and K_{i_3}=2, K_{i_4}=4, K_{i_5}=3, K_{i_6}=5 are also pairwise distinct, so this is a valid choice. The total interest in this case is 9+4+3+6+3+7=32, which is the maximum.

Sample Input 2

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

Sample Output 2

-1

There is no valid choice of six problems satisfying the conditions.

Sample Input 3

16
1 593
3 449
15 991
9 310
1 355
15 68
3 431
15 580
14 757
14 218
14 934
9 328
3 676
3 355
1 221
6 80

Sample Output 3

3971