Problem Statement

You are given two different strings S and T.
If S is lexicographically smaller than T, print Yes; otherwise, print No.

Note that many major programming languages implement lexicographical comparison of strings as operators or functions in standard libraries. For more detail, see your language's reference.

Constraints

• S and T are different strings, each of which consists of lowercase English letters and has a length of between 1 and 10 (inclusive).

Sample Input 1

abc atcoder

Sample Output 1

Yes

abc and atcoder begin with the same character, but their second characters are different. Since b comes earlier than t in alphabetical order, we can see that abc is lexicographically smaller than atcoder.

Sample Input 2

arc agc

Sample Output 2

No

Sample Input 3

a aa

Sample Output 3

Yes

Problem Statement

Takahashi came to a store to buy a pen. Here, a red pen costs R yen, a green pen costs G yen, and a blue pen costs B yen.

Takahashi dislikes the color C. If C is Red, he cannot buy a red pen; if C is Green, he cannot buy a green pen; and if C is Blue, he cannot buy a blue pen.

Determine the minimum amount of money he needs to buy one pen.

Constraints

• 1\leq R,G,B\leq 100
• R, G, and B are integers.
• C is Red, Green, or Blue.

Sample Input 1

20 30 10
Blue

Sample Output 1

20

A red pen costs 20 yen, a green pen costs 30 yen, and a blue pen costs 10 yen. Takahashi cannot buy a blue pen, but he can buy a red pen for 20 yen.

Sample Input 2

100 100 100
Red

Sample Output 2

100

Sample Input 3

37 39 93
Blue

Sample Output 3

37

Problem Statement

Takahashi is trying to create a game inspired by baseball, but he is having difficulty writing the code.
Write a program for Takahashi that solves the following problem.

There are 4 squares called Square 0, Square 1, Square 2, and Square 3. Initially, all squares are empty.
There is also an integer P; initially, P = 0.
Given a sequence of positive integers A = (A_1, A_2, \dots, A_N), perform the following operations for i = 1, 2, \dots, N in this order:

1. Put a piece on Square 0.
2. Advance every piece on the squares A_i squares ahead. In other words, if Square x has a piece, move the piece to Square (x + A_i).
   If, however, the destination square does not exist (i.e. x + A_i is greater than or equal to 4) for a piece, remove it. Add to P the number of pieces that have been removed.

Print the value of P after all the operations have been performed.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 4
• All values in input are integers.

Sample Input 1

4
1 1 3 2

Sample Output 1

3

The operations are described below. After all the operations have been performed, P equals 3.

• The operations for i=1:
  1. Put a piece on Square 0. Now, Square 0 has a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Square 1 has a piece.
• The operations for i=2:
  1. Put a piece on Square 0. Now, Squares 0 and 1 have a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Squares 1 and 2 have a piece.
• The operations for i=3:
  1. Put a piece on Square 0. Now, Squares 0, 1, and 2 have a piece.
  2. Advance every piece on the squares 3 squares ahead.
     Here, for the pieces on Squares 1 and 2, the destination squares do not exist (since 1+3=4 and 2+3=5), so remove these pieces and add 2 to P. P now equals 2. After these moves, Square 3 has a piece.
• The operations for i=4:
  1. Put a piece on Square 0. Now, Squares 0 and 3 have a piece.
  2. Advance every piece on the squares 2 squares ahead.
     Here, for the piece on Square 3, the destination square does not exist (since 3+2=5), so remove this piece and add 1 to P. P now equals 3.
     After these moves, Square 2 has a piece.

Sample Input 2

3
1 1 1

Sample Output 2

0

The value of P may not be updated by the operations.

Sample Input 3

10
2 2 4 1 1 1 4 2 2 1

Sample Output 3

8

Problem Statement

You are given an integer X not less than 2.

Find the positive integer N such that N! = X.

Here, N! denotes the factorial of N, and it is guaranteed that there is exactly one such N.

Constraints

• 2 \leq X \leq 3 \times 10^{18}
• There is exactly one positive integer N such that N!=X.
• All input values are integers.

Sample Input 1

6

Sample Output 1

3

From 3!=3\times2\times1=6, print 3.

Sample Input 2

2432902008176640000

Sample Output 2

20

From 20!=2432902008176640000, print 20.

Problem Statement

Takahashi and Aoki each have a toy made by attaching M cords to N balls.

In Takahashi's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball A_i and B_i.

Similarly, in Aoki's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball C_i and D_i.

In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.

Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence P that satisfies the conditions below.

• P is a permutation of (1, \dots, N).
• For every pair of integers i, j between 1 and N (inclusive), the following holds.
  • Balls i and j in Takahashi's toy are tied by a cord if and only if Balls P_i and P_j in Aoki's toy are tied by a cord.

If the two toys have the same shape, print Yes; otherwise, print No.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
• 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
• (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes

Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.

The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when P = (3, 2, 1, 4), for example.

Sample Input 2

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

Sample Output 2

No

The two toys do not have the same shape.

Sample Input 3

8 0

Sample Output 3

Yes

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq A_i \leq 10^{9}
• 1 \leq C_i \leq 10^{9}
• All input values are integers.

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

There are N sports players.

Among them, there are M incompatible pairs. The i-th incompatible pair (1\leq i\leq M) is the A_i-th and B_i-th players.

You will divide the players into T teams. Every player must belong to exactly one team, and every team must have one or more players. Additionally, for each i=1,2,\ldots,M, the A_i-th and B_i-th players must not belong to the same team.

Find the number of ways to satisfy these conditions. Here, two divisions are considered different when there are two players who belong to the same team in one division and different teams in the other.

Constraints

• 1\leq T\leq N\leq10
• 0\leq M\leq\dfrac{N(N-1)}2
• 1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq M)
• (A _ i,B _ i)\neq (A _ j,B _ j)\ (1\leq i\lt j\leq M)
• All input values are integers.

Sample Input 1

5 2 2
1 3
3 4

Sample Output 1

4

The following four divisions satisfy the conditions.

No other division satisfies them, so print 4.

Sample Input 2

5 1 2
1 3
3 4

Sample Output 2

0

There may be no division that satisfies the conditions.

Sample Input 3

6 4 0

Sample Output 3

65

There may be no incompatible pair.

Sample Input 4

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

Sample Output 4

8001

Problem Statement

We have a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

There are M kinds of operations available to you. Operation i swaps the a_i-th and b_i-th elements of P.

Is it possible to sort P in ascending order by doing at most 5\times 10^5 operations in total in any order?

If it is possible, give one such sequence of operations. Otherwise, report so.

Constraints

• 2\leq N \leq 1000
• P is a permutation of (1,2,\ldots,N).
• 1\leq M \leq \min(2\times 10^5, \frac{N(N-1)}{2})
• 1\leq a_i \lt b_i\leq N
• (a_i,b_i)\neq (a_j,b_j) if i\neq j.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3
4 2 1

P changes as follows: (5,3,2,4,6,1)\to (5,2,3,4,6,1)\to (5,2,3,4,1,6)\to (1,2,3,4,5,6).

Sample Input 2

5
3 4 1 2 5
2
1 3
2 5

Sample Output 2

-1

We cannot sort P in ascending order.

Sample Input 3

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

Sample Output 3

0

P may already be sorted in ascending order.

Additionally, here is another accepted output:

4
5 5 5 5

Note that it is not required to minimize the number of operations.