Problem Statement

Takahashi measured his body temperature and found it to be X {}^\circC.

Body temperature is classified into the following:

• Higher than or equal to 38.0 {}^\circC: “High fever”
• Higher than or equal to 37.5 {}^\circC and lower than 38.0 {}^\circC: “Fever”
• Lower than 37.5 {}^\circC: “Normal”

Which classification does Takahashi's body temperature fall into? Present the answer as an integer according to the Output section.

Constraints

• 30 \leq X \leq 50
• X is given to one decimal place.

Sample Input 1

40.0

Sample Output 1

1

His body temperature is 40.0 {}^\circC, which is classified as a high fever. Thus, print 1.

Sample Input 2

37.7

Sample Output 2

2

His body temperature is 37.7 {}^\circC, which is classified as a fever. Thus, print 2.

Sample Input 3

36.6

Sample Output 3

3

His body temperature is 36.6 {}^\circC, which is classified as a normal temperature. Thus, print 3.

Problem Statement

Takahashi aggregated usage records from ticket gates. However, he accidentally erased some records of entering and exiting stations. He is trying to restore the erased records.

You are given a string S consisting of i and o. We want to insert zero or more characters at arbitrary positions in S so that the resulting string satisfies the following conditions:

• Its length is even, and every odd-numbered (1st, 3rd, ...) character is i while every even-numbered (2nd, 4th, ...) character is o.

Find the minimum number of characters that need to be inserted. It can be proved under the constraints of this problem that by inserting an appropriate finite number of characters, S can be made to satisfy the conditions.

Constraints

• S is a string of length between 1 and 100, consisting of i and o.

Sample Input 1

ioi

Sample Output 1

1

We can insert o after the 3rd character to form ioio to satisfy the conditions. The conditions cannot be satisfied by inserting zero or fewer characters.

Sample Input 2

iioo

Sample Output 2

2

We can insert o after the 1st character and i after the 3rd character to satisfy the conditions. The conditions cannot be satisfied by inserting one or fewer characters.

Sample Input 3

io

Sample Output 3

0

S already satisfies the conditions.

Problem Statement

This problem is a simplified version of Problem F.

You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).

When splitting A at one position into two non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.

More formally, find the maximum sum of the following two values for an integer i such that 1 \leq i \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), and the count of distinct integers in (A_{i+1}, A_{i+2}, \ldots, A_N).

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq N (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

5

• For i=1, (3) contains 1 distinct integer, and (1,4,1,5) contains 3 distinct integers, for a total of 4.
• For i=2, (3,1) contains 2 distinct integers, and (4,1,5) contains 3 distinct integers, for a total of 5.
• For i=3, (3,1,4) contains 3 distinct integers, and (1,5) contains 2 distinct integers, for a total of 5.
• For i=4, (3,1,4,1) contains 3 distinct integers, and (5) contains 1 distinct integer, for a total of 4.

Therefore, the maximum sum is 5 for i=2,3.

Sample Input 2

10
2 5 6 5 2 1 7 9 7 2

Sample Output 2

8

Problem Statement

You are given a positive integer N. Determine whether there exists a pair of positive integers (x,y) such that x^3 - y^3 = N. If such a pair exists, print one such pair (x,y).

Constraints

• 1 \leq N \leq 10^{18}
• All input values are integers.

Sample Input 1

397

Sample Output 1

12 11

We have 12^3 - 11^3 = 397, so (x,y) = (12,11) is a solution.

Sample Input 2

1

Sample Output 2

-1

No pair of positive integers (x,y) satisfies x^3 - y^3 = 1. Thus, print -1.

Sample Input 3

39977273855577088

Sample Output 3

342756 66212

Problem Statement

You are given a tree with NK vertices. The vertices are numbered 1,2,\dots,NK, and the i-th edge (i=1,2,\dots,NK-1) connects vertices u_i and v_i bidirectionally.

Determine whether this tree can be decomposed into N paths, each of length K. More precisely, determine whether there exists an N \times K matrix P satisfying the following:

• P_{1,1}, \dots, P_{1,K}, P_{2,1}, \dots, P_{N,K} is a permutation of 1,2,\dots,NK.
• For each i=1,2,\dots,N and j=1,2,\dots,K-1, there is an edge connecting vertices P_{i,j} and P_{i,j+1}.

Constraints

• 1 \leq N
• 1 \leq K
• NK \leq 2 \times 10^5
• 1 \leq u_i < v_i \leq NK
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

It can be decomposed into a path with vertices 1,2, a path with vertices 3,4, and a path with vertices 5,6.

Sample Input 2

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

Sample Output 2

No

Problem Statement

This problem is a harder version of Problem C. Here, the sequence is split into three subarrays.

You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).

When splitting A at two positions into three non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.

More formally, find the maximum sum of the following three values for a pair of integers (i,j) such that 1 \leq i < j \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), the count of distinct integers in (A_{i+1},A_{i+2},\ldots,A_j), and the count of distinct integers in (A_{j+1},A_{j+2},\ldots,A_{N}).

Constraints

• 3 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq N (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

5

If we let (i,j) = (2,4) to split the sequence into three subarrays (3,1), (4,1), (5), the counts of distinct integers in those subarrays are 2, 2, 1, respectively, for a total of 5. This sum cannot be greater than 5, so the answer is 5. Other partitions, such as (i,j) = (1,3), (2,3), (3,4), also achieve this sum.

Sample Input 2

10
2 5 6 4 4 1 1 3 1 4

Sample Output 2

9

Problem Statement

You are given a directed graph with N vertices and M edges. The vertices are numbered 1,2,\dots,N. Edge j (j=1,2,\dots,M) goes from vertex u_j to vertex v_j. It is guaranteed that vertex N is reachable from vertex 1.

Initially, all edges have weight 0. We choose exactly K out of the M edges and change their weights to 1. Find the maximum possible value of the shortest distance from vertex 1 to vertex N in the resulting graph.

Constraints

• 2 \leq N \leq 30
• 1 \leq K \leq M \leq 100
• 1 \leq u_j, v_j \leq N
• u_j \neq v_j
• In the given graph, vertex N is reachable from vertex 1.
• All input values are integers.

Sample Input 1

3 3 2
1 2
2 3
1 3

Sample Output 1

1

By choosing edges 1,3, the shortest distance from vertex 1 to vertex 3 becomes 1. There is no way to make the shortest distance 2 or greater, so the answer is 1.

Sample Input 2

4 4 3
1 2
1 3
3 2
2 4

Sample Output 2

2

By choosing edges 1,2,4, the shortest distance from vertex 1 to vertex 4 becomes 2. There is no way to make the shortest distance 3 or greater, so the answer is 2.

Sample Input 3

2 2 1
1 2
1 2

Sample Output 3

0

Note that there may be multi-edges.