Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N and positive integers P,Q,R, and S.
Here, P,Q,R, and S satisfy 1\leq P\leq Q<R\leq S \leq N and Q-P=S-R.

Let B=(B_1, B_2,\ldots, B_N) be the sequence obtained by swapping the P-th through Q-th terms and the R-th through S-th terms of A.
Print the sequence B.

Constraints

• 1\leq N \leq 100
• 1\leq A_i\leq 100
• 1\leq P\leq Q<R\leq S \leq N
• Q-P=S-R
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

5 6 7 4 1 2 3 8

Swapping the 1-st through 3-rd terms (1,2,3) and the 5-th through 7-th terms (5,6,7) of the sequence A=(1,2,3,4,5,6,7,8) results in B=(5,6,7,4,1,2,3,8), which should be printed with spaces in between.

Sample Input 2

5 2 3 4 5
2 2 1 1 1

Sample Output 2

2 1 1 2 1

The same integer may occur multiple times in the sequence.

Sample Input 3

2 1 1 2 2
50 100

Sample Output 3

100 50

Sample Input 4

10 2 4 7 9
22 75 26 45 72 81 47 29 97 2

Sample Output 4

22 47 29 97 72 81 75 26 45 2

Problem Statement

You are given an integer sequence A=(A_1,A_2,A_3,A_4,A_5) obtained by permuting (1,2,3,4,5).

Determine whether A can be sorted in ascending order by performing exactly one operation of swapping two adjacent elements in A.

Constraints

• A is an integer sequence of length 5 obtained by permuting (1,2,3,4,5).

Sample Input 1

1 2 4 3 5

Sample Output 1

Yes

By swapping A_3 and A_4, A becomes (1,2,3,4,5), so it can be sorted in ascending order. Therefore, print Yes.

Sample Input 2

5 3 2 4 1

Sample Output 2

No

No matter what operation is performed, it is impossible to sort A in ascending order.

Sample Input 3

1 2 3 4 5

Sample Output 3

No

You must perform exactly one operation.

Sample Input 4

2 1 3 4 5

Sample Output 4

Yes

Problem Statement

There is a black-and-white image of height H pixels and width W pixels. The color of the pixel at the i-th row from the top and j-th column from the left is given as a character C_{i,j}, where . represents white and # represents black.

From the top, bottom, left, and right edges of this image, remove rows and columns where all pixels are white. Specifically, perform the following operations in order:

1. While the topmost row of the image is entirely white, repeat removing the topmost row.
2. While the bottommost row of the image is entirely white, repeat removing the bottommost row.
3. While the leftmost column of the image is entirely white, repeat removing the leftmost column.
4. While the rightmost column of the image is entirely white, repeat removing the rightmost column.

Output the image after processing.

The given image contains at least one black pixel.

Constraints

• 1 \le H, W \le 50
• C_{i,j} is . or #.
• At least one black pixel exists.

Sample Input 1

4 5
.....
..#..
.###.
.....

Sample Output 1

.#.
###

You should remove one row from the top edge, one row from the bottom edge, one column from the left edge, and one column from the right edge.

Sample Input 2

3 4
#...
....
...#

Sample Output 2

#...
....
...#

In this image, all of the topmost row, bottommost row, leftmost column, and rightmost column contain black pixels.
Therefore, without removing any rows or columns, you should output the original image as is.

Sample Input 3

5 6
......
......
...#..
......
......

Sample Output 3

#

Problem Statement

There are N types of elements numbered 1, 2, \ldots, N.

Elements can be combined with each other. When elements i and j are combined, they transform into element A_{i, j} if i \geq j, and into element A_{j, i} if i < j.

Starting with element 1, combine it with elements 1, 2, \ldots, N in this order. Find the final element obtained.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_{i, j} \leq N
• All input values are integers.

Sample Input 1

4
3
2 4
3 1 2
2 1 2 4

Sample Output 1

2

• Combining element 1 with element 1 results in element 3.

• Combining element 3 with element 2 results in element 1.

• Combining element 1 with element 3 results in element 3.

• Combining element 3 with element 4 results in element 2.

Therefore, the value to be printed is 2.

Sample Input 2

5
5
5 5
5 5 5
5 5 5 5
5 5 5 5 5

Sample Output 2

5

Sample Input 3

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

Sample Output 3

5

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is simple.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

2

One way to remove cycles from the graph is to delete the two edges between vertex 1 and vertex 2 and between vertex 4 and vertex 5.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print 2.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

0

Sample Input 3

5 3
1 2
1 3
2 3

Sample Output 3

1

Problem Statement

There are N researchers, numbered 1, 2, \ldots, N.

There are M conflicts of interest among the researchers; for i = 1, 2, \ldots, M, researchers A_i and B_i have a conflict of interest with each other.

The reviewers of a paper must be three distinct researchers who are different from the author of the paper and have no conflict of interest with the author.

For i = 1, 2, \ldots, N, solve the following problem:

• Find the number of possible triples of reviewers for a paper authored by researcher i.

Assume that all papers are single-authored.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• (A_i, B_i) \neq (A_j, B_j) if i \neq j.
• (A_i, B_i) \neq (B_j, A_j) if i \neq j.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0 1 0 4 4 10

Below, we represent a set of researchers by the set of their numbers.

• There are no possible triples of reviewers for a paper authored by researcher 1.

• The possible triple of reviewers for a paper authored by researcher 2 is \lbrace 4, 5, 6 \rbrace, which is 1 triple.

• There are no possible triples of reviewers for a paper authored by researcher 3.

• The possible triples of reviewers for a paper authored by researcher 4 are \lbrace 2, 3, 5 \rbrace, \lbrace 2, 3, 6 \rbrace, \lbrace 2, 5, 6 \rbrace, \lbrace 3, 5, 6 \rbrace, which is 4 triples.

• The possible triples of reviewers for a paper authored by researcher 5 are \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 6 \rbrace, \lbrace 1, 4, 6 \rbrace, \lbrace 2, 4, 6 \rbrace, which is 4 triples.

• The possible triples of reviewers for a paper authored by researcher 6 are \lbrace 1, 2, 3 \rbrace, \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 5 \rbrace, \lbrace 1, 3, 4 \rbrace, \lbrace 1, 3, 5 \rbrace, \lbrace 1, 4, 5 \rbrace, \lbrace 2, 3, 4 \rbrace, \lbrace 2, 3, 5 \rbrace, \lbrace 2, 4, 5 \rbrace, \lbrace 3, 4, 5 \rbrace, which is 10 triples.

Sample Input 2

7 3
1 2
3 4
5 6

Sample Output 2

10 10 10 10 10 10 20

Sample Input 3

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

Sample Output 3

1 0 0 1 0 1

Problem Statement

There is a perfect binary tree with 2^{10^{100}}-1 vertices, numbered 1,2,...,2^{10^{100}}-1.
Vertex 1 is the root. For each 1\leq i < 2^{10^{100}-1}, Vertex i has two children: Vertex 2i to the left and Vertex 2i+1 to the right.

Takahashi starts at Vertex X and performs N moves, represented by a string S. The i-th move is as follows.

• If the i-th character of S is U, go to the parent of the vertex he is on now.
• If the i-th character of S is L, go to the left child of the vertex he is on now.
• If the i-th character of S is R, go to the right child of the vertex he is on now.

Find the index of the vertex Takahashi will be on after N moves. In the given cases, it is guaranteed that the answer is at most 10^{18}.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq X \leq 10^{18}
• N and X are integers.
• S has a length of N and consists of U, L, and R.
• When Takahashi is at the root, he never attempts to go to the parent.
• When Takahashi is at a leaf, he never attempts to go to a child.
• The index of the vertex Takahashi is on after N moves is at most 10^{18}.

Sample Input 1

3 2
URL

Sample Output 1

6

The perfect binary tree has the following structure.

In the three moves, Takahashi goes 2 \to 1 \to 3 \to 6.

Sample Input 2

4 500000000000000000
RRUU

Sample Output 2

500000000000000000

During the process, Takahashi may be at a vertex whose index exceeds 10^{18}.

Sample Input 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

Sample Output 3

126419752371

Problem Statement

There is a simple undirected graph with N vertices and M edges, where vertices are numbered from 1 to N, and edges are numbered from 1 to M. Edge i connects vertex a_i and vertex b_i.
K security guards numbered from 1 to K are on some vertices. Guard i is on vertex p_i and has a stamina of h_i. All p_i are distinct.

A vertex v is said to be guarded when the following condition is satisfied:

• there is at least one guard i such that the distance between vertex v and vertex p_i is at most h_i.

Here, the distance between vertex u and vertex v is the minimum number of edges in the path connecting vertices u and v.

List all guarded vertices in ascending order.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \left(\frac{N(N-1)}{2}, 2 \times 10^5 \right)
• 1 \leq K \leq N
• 1 \leq a_i, b_i \leq N
• The given graph is simple.
• 1 \leq p_i \leq N
• All p_i are distinct.
• 1 \leq h_i \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

4
1 2 3 5

The guarded vertices are 1, 2, 3, 5.
These vertices are guarded because of the following reasons.

• The distance between vertex 1 and vertex p_1 = 1 is 0, which is not greater than h_1 = 1. Thus, vertex 1 is guarded.
• The distance between vertex 2 and vertex p_1 = 1 is 1, which is not greater than h_1 = 1. Thus, vertex 2 is guarded.
• The distance between vertex 3 and vertex p_2 = 5 is 1, which is not greater than h_2 = 2. Thus, vertex 3 is guarded.
• The distance between vertex 5 and vertex p_1 = 1 is 1, which is not greater than h_1 = 1. Thus, vertex 5 is guarded.

Sample Input 2

3 0 1
2 3

Sample Output 2

1
2

The given graph may have no edges.

Sample Input 3

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

Sample Output 3

7
1 2 3 5 6 8 9

Problem Statement

There are N towns numbered 1,\ldots,N and M roads numbered 1,\ldots,M.

Road i connects towns A_i and B_i. When you use a road, your score changes as follows:

• when you move from town A_i to town B_i using road i, your score increases by C_i; when you move from town B_i to town A_i using road i, your score decreases by C_i.

Your score may become negative.

Answer the following Q questions.

• If you start traveling from town X_i with initial score 0, find the maximum possible score when you are at town Y_i.
  Here, if you cannot get from town X_i to town Y_i, print nan instead; if you can have as large a score as you want when you are at town Y_i, print inf instead.

Constraints

• 2\leq N \leq 10^5
• 0\leq M \leq 10^5
• 1\leq Q \leq 10^5
• 1\leq A_i,B_i,X_i,Y_i \leq N
• 0\leq C_i \leq 10^9
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

-2
inf
nan

For the first question, if you use road 5 to move from town 5 to town 3, you can have a score -2 when you are at town 3.
Since you cannot make the score larger, the answer is -2.

For the second question, you can have as large a score as you want when you are at town 2 if you travel as follows: repeatedly "use road 2 to move from town 1 to town 2 and then use road 1 to move from town 2 to town 1" as many times as you want, and finally use road 2 to move from town 1 to town 2.

For the third question, you cannot get from town 3 to town 1.

Sample Input 2

2 1 1
1 1 1
1 1

Sample Output 2

inf

The endpoints of a road may be the same, and so may the endpoints given in a question.

Sample Input 3

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

Sample Output 3

inf
nan
nan
inf
-9