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 of length 16 consisting of 0 and 1.

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Constraints

• S is a string of length 16 consisting of 0 and 1.

Sample Input 1

1001000000001010

Sample Output 1

No

The 4-th character of S= 1001000000001010 is 1, so you should print No.

Sample Input 2

1010100000101000

Sample Output 2

Yes

Every even-positioned character in S= 1010100000101000 is 0, so you should print Yes.

Sample Input 3

1111111111111111

Sample Output 3

No

Every even-positioned character in S is 1. Particularly, they are not all 0, so you should print No.

Problem Statement

There are N competitive programmers numbered person 1, person 2, \ldots, and person N.
There is a relation called superiority between the programmers. For all pairs of distinct programmers (person X, person Y), exactly one of the following two relations holds: "person X is stronger than person Y" or "person Y is stronger than person X."
The superiority is transitive. In other words, for all triplets of distinct programmers (person X, person Y, person Z), it holds that:

• if person X is stronger than person Y and person Y is stronger than person Z, then person X is stronger than person Z.

A person X is said to be the strongest programmer if person X is stronger than person Y for all people Y other than person X. (Under the constraints above, we can prove that there is always exactly one such person.)

You have M pieces of information on their superiority. The i-th of them is that "person A_i is stronger than person B_i."
Can you determine the strongest programmer among the N based on the information?
If you can, print the person's number. Otherwise, that is, if there are multiple possible strongest programmers, print -1.

Constraints

• 2 \leq N \leq 50
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• If i \neq j, then (A_i, B_i) \neq (A_j, B_j).
• There is at least one way to determine superiorities for all pairs of distinct programmers, that is consistent with the given information.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1

You have two pieces of information: "person 1 is stronger than person 2" and "person 2 is stronger than person 3."
By the transitivity, you can also infer that "person 1 is stronger than person 3," so person 1 is the strongest programmer.

Sample Input 2

3 2
1 3
2 3

Sample Output 2

-1

Both person 1 and person 2 may be the strongest programmer. Since you cannot uniquely determine which is the strongest, you should print -1.

Sample Input 3

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

Sample Output 3

-1

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

• 2 \le N \le 100
• 0 \le A_{i,j} \le 1(1 \le i,j \le N)
• All input values are integers.

Sample Input 1

4
0101
1101
1111
0000

Sample Output 1

1010
1101
0111
0001

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

5
01010
01001
10110
00110
01010

Sample Output 3

00101
11000
00111
00110
10100

Problem Statement

The AtCoder Restaurant uses N types of ingredients numbered from 1 to N.

The restaurant offers M dishes numbered from 1 to M. Dish i uses K_i types of ingredients, namely A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}.

Snuke currently dislikes all N ingredients. He cannot eat any dish that uses one or more ingredients he dislikes, and he can eat a dish that uses none of the disliked ingredients.

Over the next N days, he will overcome his dislikes one ingredient per day. On day i, he overcomes ingredient B_i, and from then on he no longer dislikes it.

For each i=1,2,\ldots,N, find:

• the number of dishes at the AtCoder Restaurant that he can eat immediately after overcoming ingredient B_i on day i.

Constraints

• 1 \leq N \leq 3 \times 10^{5}
• 1 \leq M \leq 3 \times 10^{5}
• 1 \leq K_i \leq N (1 \leq i \leq M)
• The sum of K_i is at most 3 \times 10^{5}.
• 1 \leq A_{i,j} \leq N (1 \leq i \leq M, 1 \leq j \leq K_i)
• A_{i,j} \neq A_{i,k} (1 \leq i \leq M, j \neq k)
• 1 \leq B_i \leq N (1 \leq i \leq N)
• B_i \neq B_j (i \neq j )
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
1
2
3
4

Snuke overcomes his disliked ingredients as follows:

• Day 1: He overcomes ingredient 1. At this time, every dish still uses a disliked ingredient, so print 0.
• Day 2: He overcomes ingredient 3. Dish 4 no longer uses any disliked ingredient and becomes edible; all other dishes still use disliked ingredients, so print 1.
• Day 3: He overcomes ingredient 2. Dish 1 no longer uses any disliked ingredient and becomes edible; all dishes except 1 and 4 still use disliked ingredients, so print 2.
• Day 4: He overcomes ingredient 5. Dish 3 no longer uses any disliked ingredient and becomes edible; all dishes except 1, 3, and 4 still use disliked ingredients, so print 3.
• Day 5: He overcomes ingredient 4. Dish 2 no longer uses any disliked ingredient and becomes edible; now all dishes have no disliked ingredients, so print 4.

Sample Input 2

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

Sample Output 2

0
0
1
1
1
2
4
6
8

Problem Statement

A region has N towns numbered 1 to N, and M roads numbered 1 to M.

The i-th road connects town A_i and town B_i bidirectionally with length C_i.

Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• The pairs (A_i,B_i) are distinct.
• 1\leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

Sample Output 1

1110

If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.

Sample Input 2

10 1
5 9 1

Sample Output 2

1

There may be a town that is not connected to a road.

Sample Input 3

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

Sample Output 3

20

Problem Statement

You are given a string S consisting of uppercase English letters.

Find the number of integer triples (i, j, k) satisfying both of the following conditions:

• 1 \leq i < j < k \leq |S|
• The length-3 string formed by concatenating S_i, S_j, and S_k in this order is a palindrome.

Here, |S| denotes the length of S, and S_x denotes the x-th character of S.

Constraints

• S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of uppercase English letters.

Sample Input 1

ABCACC

Sample Output 1

5

The triples satisfying the conditions are (i, j, k) = (1, 2, 4), (1, 3, 4), (3, 4, 5), (3, 4, 6), (3, 5, 6).

Sample Input 2

OOOOOOOO

Sample Output 2

56

Sample Input 3

XYYXYYXYXXX

Sample Output 3

75

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges, where vertices are numbered 1 to N and edges are numbered 1 to M. Edge i (1 \leq i \leq M) connects vertices u_i and v_i bidirectionally and has weight w_i.

For a path, define its weight as the maximum weight of an edge in the path. Define f(x, y) as the minimum possible path weight of a path from vertex x to vertex y.

You are given two sequences of length K: (A_1, A_2, \ldots, A_K) and (B_1, B_2, \ldots, B_K). It is guaranteed that A_i \neq B_j (1 \leq i,j \leq K).

Permute the sequence B freely so that \displaystyle \sum_{i=1}^{K} f(A_i, B_i) is minimized.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq \min(\frac{N \times (N-1)}{2},2 \times 10^5)
• 1 \leq K \leq N
• 1 \leq u_i<v_i \leq N (1 \leq i \leq M)
• 1 \leq w_i \leq 10^9
• 1 \leq A_i,B_i \leq N (1 \leq i \leq K)
• The given graph is simple and connected.
• All input values are integers.

Sample Input 1

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

Sample Output 1

8

If we rearrange B as (2,4,4):

• f(1,2) = 5: The path from vertex 1 to vertex 2 passing through vertex 4 contains edge 3 with a maximum edge weight of 5. There is no path with a maximum edge weight less than or equal to 4, so 5 is the minimum possible.
• f(1,4) = 2: The path from vertex 1 to vertex 4 passing through vertex 3 contains edge 1 with a maximum edge weight of 2. There is no path with a maximum edge weight less than or equal to 1, so 2 is the minimum possible.
• f(3,4) = 1: The path from vertex 3 to vertex 4 passing through the direct edge contains an edge with a maximum edge weight of 1. No path can have a maximum weight 0 or less, so 1 is the minimum possible.

Thus, \displaystyle \sum_{i=1}^{3} f(A_i, B_i) = 5+2+1=8. No permutation of B yields 7 or less, so the answer is 8.

Sample Input 2

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

Sample Output 2

3

Problem Statement

There are N people standing in a line, with person i standing at the i-th position from the front.

Repeat the following operation until there is only one person left in the line:

• Remove the person at the front of the line with a probability of \frac{1}{2}, otherwise move them to the end of the line.

For each person i=1,2,\ldots,N, find the probability that person i is the last person remaining in the line, modulo 998244353. (All choices to remove or not are random and independent.)

Constraints

• 2\leq N\leq 3000
• All input values are integers.

Sample Input 1

2

Sample Output 1

332748118 665496236

Person 1 will be the last person remaining in the line with probability \frac{1}{3}.

Person 2 will be the last person remaining in the line with probability \frac{2}{3}.

Sample Input 2

5

Sample Output 2

235530465 792768557 258531487 238597268 471060930