Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
• All values in the input are integers.
• The graph given in the input is simple.

Sample Input 1

4 3
1 3
4 2
3 2

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

Sample Input 3

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

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

1. Let N be the current length of S, and S = S_1S_2\ldots S_N.
2. Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)
3. Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

• Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

• First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
• Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
• Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

Problem Statement

There is a grid with N rows and N columns, where N is an odd number at most 45.

Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.

In this grid, you will place Takahashi and a dragon consisting of N^2-1 parts numbered 1 to N^2-1 in such a way that satisfies the following conditions:

• Takahashi must be placed at the center of the grid, that is, in cell (\frac{N+1}{2},\frac{N+1}{2}).
• Except for the cell where Takahashi is, exactly one dragon part must be placed in each cell.
• For every integer x satisfying 2 \leq x \leq N^2-1, the dragon part x must be placed in a cell adjacent by an edge to the cell containing part x-1.
  • Cells (i,j) and (k,l) are said to be adjacent by an edge if and only if |i-k|+|j-l|=1.

Print one way to arrange the parts to satisfy the conditions. It is guaranteed that there is at least one arrangement that satisfies the conditions.

Constraints

• 3 \leq N \leq 45
• N is odd.

Sample Input 1

5

Sample Output 1

1 2 3 4 5
16 17 18 19 6
15 24 T 20 7
14 23 22 21 8
13 12 11 10 9

The following output also satisfies all the conditions and is correct.

9 10 11 14 15
8 7 12 13 16
5 6 T 18 17
4 3 24 19 20 
1 2 23 22 21

On the other hand, the following outputs are incorrect for the reasons given.

Takahashi is not at the center.

1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 T

The cells containing parts 23 and 24 are not adjacent by an edge.

1 2 3 4 5
10 9 8 7 6
11 12 24 22 23
14 13 T 21 20
15 16 17 18 19

Problem Statement

On a coordinate plane, there are N points P_1, P_2, \ldots, P_N, where point P_i has coordinates (X_i, Y_i).
The distance \text{dist}(A, B) between two points A and B is defined as follows:

A rabbit is initially at point A.
A rabbit at position (x, y) can jump to (x+1, y+1), (x+1, y-1), (x-1, y+1), or (x-1, y-1) in one jump.
\text{dist}(A, B) is defined as the minimum number of jumps required to get from point A to point B.
If it is impossible to get from point A to point B after any number of jumps, let \text{dist}(A, B) = 0.

Calculate the sum \displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i, P_j).

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq X_i, Y_i \leq 10^8
• For i \neq j, (X_i, Y_i) \neq (X_j, Y_j)
• All input values are integers.

Sample Input 1

3
0 0
1 3
5 6

Sample Output 1

3

P_1, P_2, and P_3 have coordinates (0,0), (1,3), and (5,6), respectively.
The rabbit can get from P_1 to P_2 in three jumps via (0,0) \to (1,1) \to (0,2) \to (1,3), but not in two or fewer jumps,
so \text{dist}(P_1, P_2) = 3.
The rabbit cannot get from P_1 to P_3 or from P_2 to P_3, so \text{dist}(P_1, P_3) = \text{dist}(P_2, P_3) = 0.

Therefore, the answer is \displaystyle\sum_{i=1}^{2}\displaystyle\sum_{j=i+1}^3\text{dist}(P_i, P_j)=\text{dist}(P_1, P_2)+\text{dist}(P_1, P_3)+\text{dist}(P_2, P_3)=3+0+0=3.

Sample Input 2

5
0 5
1 7
2 9
3 8
4 6

Sample Output 2

11

Problem Statement

As the factory manager of Keyence, you want to monitor several sections on a conveyor belt. There are a total of N sections you want to monitor, and the length of the i-th section is D_i meters.

There are two types of sensors to choose from, and below is some information about each sensor.

• Type-j sensor (1\leq j \leq 2): Can monitor a section of length L_j meters. The price is C_j per sensor, and you can use at most K_j sensors of this type in total.

You can divide one section into several sections for monitoring. It is fine if the sections monitored by the sensors overlap, or if they monitor more than the length of the section you want to monitor. For example, when L_1=4 and L_2=2, you can use one type-1 sensor to monitor a section of length 3 meters, or use one type-1 and one type-2 sensor to monitor a section of length 5 meters.

Determine whether it is possible to monitor all N sections, and if it is possible, find the minimum total cost of the necessary sensors.

Constraints

• 1\leq N \leq 100
• 1\leq D_i,L_j \leq 10^5
• 1\leq C_j \leq 10^9
• 1\leq K_j \leq 10^3
• All input values are integers.

Sample Input 1

3
3 5 10
4 3 3
2 2 6

Sample Output 1

17

You can monitor all sections by using three type-1 sensors and four type-2 sensors as follows.

• Use one type-1 sensor to monitor the first section.
• Use one type-1 and one type-2 sensor to monitor the second section.
• Use one type-1 and three type-2 sensors to monitor the third section.

In this case, the total cost of the necessary sensors is 3\times 3 + 2\times 4 = 17, which is the minimum.

Sample Input 2

3
3 5 10
4 3 3
2 2 3

Sample Output 2

-1

Sample Input 3

2
4 8
3 1 100
4 10000 100

Sample Output 3

5

It is fine if one type of sensor is not used at all.