Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string S of length 8 consisting of digits and -s (hyphens).

Determine whether S satisfies the following conditions:

• the fourth character is -;
• the other characters are all digits.

Constraints

• S is a string of length 8 consisting of digits and -s.

Sample Input 1

160-0022

Sample Output 1

Yes

Sample Input 2

1600022-

Sample Output 2

No

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Takahashi typed a string S satisfying the following conditions:

• S is a concatenation of one or more strings, each of which is past or post;
• at most one of the concatenated strings is post.

Your task is to find out which of the concatenated strings is post.

Constraints

• |S| \le 1000
• S is a concatenation of one or more strings, each of which is past or post.
• At most one of the concatenated strings is post.

Sample Input 1

pastpastpostpast

Sample Output 1

3

We have S= pastpastpostpast, where the third string concatenated is post.

Sample Input 2

pastpastpast

Sample Output 2

none

We have S= pastpastpast, where none of the strings concatenated is post.

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

A company sells N types of cellphones, called Type 1 through Type N.
Also, there are M frequency bands used for cellular networks, called Band 1 through Band M.
A cellphone of Type i can only use K_i of those bands: Bands A_{i, 1}, A_{i, 2}, A_{i, 3}, \dots, A_{i, K_i}.
You will buy a cellphone by this company that satisfies the following condition:

• The cellphone can use Q or more of the following P bands: Bands B_1, B_2, B_3, \dots, B_P.

Print the number of types of such cellphones.

Constraints

• 1 \le N \le 50
• 1 \le M \le 50
• 1 \le K_i \le M
• 1 \le A_{i, j} \le M
• A_{i, j} \neq A_{i, k} for j \neq k
• 1 \le Q \le P \le M
• 1 \le B_i \le M
• B_i \neq B_j for i \neq j
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

Each type of cellphone can use the following bands:

• Type 1: Bands 4
• Type 2: Bands 1, 3
• Type 3: Bands 1, 2, 3
• Type 4: Bands 2, 4

The types that can use one or more of Bands 2, 4 are Types 1, 3, 4.

Sample Input 2

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

Sample Output 2

3

Types 1, 3, 4 are desirable.

Sample Input 3

1 2
1 1
1 1
2

Sample Output 3

0

There can be no desirable types.

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given are a length-N sequence A=(A_1,A_2,...,A_N) and an integer K between 1 and N (inclusive).

For every integer x from 1 through N-K+1, find the following:

• \displaystyle \sum_{i=x}^{x+K-1} A_i, that is, the sum of K elements from A_x through A_{x+K-1}.

Constraints

• All values in input are integers.
• 1 \le K \le N \le 5 \times 10^5
• |A_i| \le 10^9 (1 \le i \le N)

Sample Input 1

6 3
2 0 2 -1 0 -4

Sample Output 1

4
1
1
-5

• The sum for x=1 is A_1 + A_2 + A_3 = 4.
• The sum for x=2 is A_2 + A_3 + A_4 = 1.
• The sum for x=3 is A_3 + A_4 + A_5 = 1.
• The sum for x=4 is A_4 + A_5 + A_6 = -5.

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a sequence A, which is initially empty. You are given a string S of length N consisting of A, B, C, D, E, F, L, and R.
Let S_i denotes the i-th character of S.
For each i = 1, 2, 3, \dots, N in this order, do as follows:

• If S_i is L: insert i at the beginning of A.
• If S_i is R: insert i at the end of A.
• If S_i is A: if the length of A is less than 1, print ERROR; otherwise, print the first number from the beginning of A and delete it.
• If S_i is B: if the length of A is less than 2, print ERROR; otherwise, print the second number from the beginning of A and delete it.
• If S_i is C: if the length of A is less than 3, print ERROR; otherwise, print the third number from the beginning of A and delete it.
• If S_i is D: if the length of A is less than 1, print ERROR; otherwise, print the first number from the end of A and delete it.
• If S_i is C: if the length of A is less than 2, print ERROR; otherwise, print the second number from the end of A and delete it.
• If S_i is C: if the length of A is less than 3, print ERROR; otherwise, print the third number from the end of A and delete it.

Constraints

• 1 ≤ N ≤ 3 \times 10^5
• S is a string of length N consisting of A, B, C, D, E, F, L, and R.

Sample Input 1

11
LLRLRCDEFBA

Sample Output 1

1
5
2
ERROR
3
4

The process goes as follows:

• S_1 is L, so we insert 1 at the beginning. A = (1) now.
• S_2 is L, so we insert 2 at the beginning. A = (2, 1) now.
• S_3 is R, so we insert 3 at the end. A = (2, 1, 3) now.
• S_4 is L, so we insert 4 at the beginning. A = (4, 2, 1, 3) now.
• S_5 is R, so we insert 5 at the beginning. A = (4, 2, 1, 3, 5) now.
• S_6 is C, so we delete the third number from the beginning: 1. A = (4, 2, 3, 5) now.
• S_7 is D, so we delete the first number from the end: 5. A = (4, 2, 3) now.
• S_8 is E, so we delete the second number from the end: 2. A = (4, 3) now.
• S_9 is F, but we have less than 3 numbers, so we print ERROR.
• S_{10} is B, so we delete the second number from the beginning: 3. A = (4) now.
• S_{11} is A, so we delete the first number from the beginning: 4. A = () now.

Sample Input 2

36
RLLDBBDDLCLDFRLRRLRRFLRDRLALLELCAARF

Sample Output 2

1
2
ERROR
3
ERROR
ERROR
9
ERROR
17
23
26
20
28
31
29
19

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You have invented a new epoch-making computer, which you will use to process N tasks.
The computer takes A_i seconds to process the i-th task. Additionally, each task has a value called the load; the load of the i-th task is B_i. The computer will process the tasks in the given order without pause.
At the moment when the computer has processed tasks of load L or higher for T consecutive seconds, the safety system halts the processing for X seconds, and then the computer restarts processing. Here, if the computer was in the middle of processing a task when interrupted, the computer has to process that task again from the beginning.
Determine whether the computer completes all tasks in finite time, and find that time needed if it is finite. If the safety system activates at the moment when the final task is finished, include that halt in the answer.

Constraints

• 1 \le N \le 100
• 1 \le L \le 1000
• 1 \le T \le 1000
• 1 \le X \le 1000
• 1 \le A_i \le 1000
• 1 \le B_i \le 1000
• All values in input are integers.

Sample Input 1

4 10 3 5
2 15
2 10
2 20
2 5

Sample Output 1

20

Since the 1-st and 2-nd tasks both have loads 10 or higher, at the moment when the computer has processed the 2-nd for 1 second after finishing the 1-st, it has processed tasks of load L or higher for 3 seconds, so it halts for 5 seconds.
Then, the computer starts processing the 2-nd task again from the beginning. The 3-rd task also has a load not lower than 10, so at the moment when the computer has processed it for 1 second, the safety system activates again and makes the computer halt for 5 seconds.
Then, the computer starts processing the 3-nd task again from the beginning. The 4-th task has a load lower than 10, so now the computer takes 2 seconds for each of the 3-rd and 4-th tasks, and all tasks are done.
At the end of the 1-st halt, 8 seconds have passed; at the end of the 2-nd halt, 16 seconds have passed; at the end of processing all tasks, 20 seconds have passed.

Sample Input 2

1 1 1 1
100 100

Sample Output 2

forever

The safety system activates in the middle of processing the first task, making the computer start over, and it repeats forever.

Sample Input 3

4 10 5 10
3 5
5 20
3 10
2 10

Sample Output 3

33

At the moment when the 2-nd task is finished, the safety system activates once. Since the computer was not in the middle of processing a task when interrupted, it starts processing the 3-rd task after the halt.
Then, at the moment when the final task is finished, the safety system activates again.
As noted at the end of Problem Statement, we include this second halt in the answer.

Sample Input 4

3 10 5 10
3 10
3 9
3 10

Sample Output 4

9

There is no moment when tasks of loads 10 or higher continue for 5 or more consecutive seconds, so the safety system never activates.

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

In some country, there are N cities called City 1 through City N and M roads called Road 1 through Road N.
Road i connects City A_i and City B_i bidirectionally, and it takes C_i units of time to traverse it.
In City 1, you will start a Q-day trip. On the i-th day, you do one of the following actions:

• Do nothing.
• Choose one of the roads that go from the city you are in, and traverse that road to reach the city at the other end. Here, it must take at most X_i units of time to traverse the chosen road.

For each integer i from 1 through Q, find the number of cities that you are potentially in at the i-th night.
Assume that one unit of time is shorter than \frac{1}{10^{100}} days.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le M \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i < B_i \le N
• (A_i, B_i) \neq (A_j, B_j) for i \neq j
• 1 \le C_i \le 10^9
• 1 \le X_i \le 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
2
3
3

• Day 1:
  There are no roads that go from City 1 and take at most 2 units of time to traverse, so you have to stay there.
  There is just one city that you are potentially in at night: City 1.
• Day 2:
  Only Road 2 is available, which takes you to City 3. You can also choose to stay at City 1.
  There are two cities that you are potentially in at night: City 1 and 3.
• Day 3:
  Roads 2 and 3 are available (if you are in a city they go from). If you moved to City 3 the previous day, you can use Road 3 to reach City 2 this day.
  There are three cities that you are potentially in at night: City 1, 2, and 3.
• Day 4:
  All roads are available, but there are still three cities that you are potentially in at night: City 1, 2, and 3.

Sample Input 2

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

Sample Output 2

2
3
4
4
5

Note that you cannot traverse multiple roads in a day.

Sample Input 3

4 1 3
1 4 100
50 100 1000000000

Sample Output 3

1
2
2

There may be cities unreachable by roads.

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

A convenience store Can-Can-Mart sells N cans.
The i-th can is sold for P_i yen, and you need a can opener to open it if T_i = 1; you can open it without an opener if T_i = 0.
You can buy any number of openers for Q yen each. An opener can be used to open K cans, after which it gets broken and unusable.
You will choose M of the N cans and buy them, along with openers needed to open them. Find the minimum total amount of money needed for this.

Constraints

• All values in input are integers.
• 1 \le M \le N \le 10^5
• 1 \le K \le N
• 1 \le Q \le 10^9
• 1 \le P_i \le 10^9, T_i \in \{0,1\} (1 \le i \le N)

Sample Input 1

6 3 2 10
15 1
25 0
20 0
10 1
5 1
20 0

Sample Output 1

45

For example, you can buy the 3-rd, 4-th, 5-th cans, and one opener to make the total cost 45 yen. We can show that there is no way that costs less.

Sample Input 2

5 2 5 40
120 0
1 1
90 0
10 0
50 0

Sample Output 2

51

Even if we have just one can that needs an opener and K = 5, we have to buy one opener.

Sample Input 3

16 9 1 631593942
758234071 1
872232933 0
928146137 0
141777768 0
339097211 1
590423762 1
656886697 1
164443392 0
181259343 0
509224290 0
973377384 0
934014075 1
167877698 1
549037938 0
94228809 1
898548470 0

Sample Output 3

4841818525

The answer can be enormous.

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

In the PAST Island, there is a fishing pond, which is divided into H horizontal rows and W vertical columns of squares on the map. The deliciousness of a fish in Square (i, j) is A_{i,j}.

Initially, you are in Square (1, 1). Now, you will do fishing as follows:

• Let (p, q) be the square you are currently in.
• You catch zero or one fish in (p, q).
• Then, you move as follows:
  • if (p, q) = (H, W), you end fishing;
  • otherwise, move to Square (p+1, q) or Square (p, q+1). However,
    • if p = H, you cannot move to Square (p+1, q);
    • if q = W, you cannot move to Square (p, q+1).

For every integer k from 1 through H+W-1, solve the following problem:

• find the maximum possible total deliciousness of fish you catch when you are allowed to catch at most k fish in total.

Constraints

• All values in input are integers.
• 1 \le H,W \le 100
• 1 \le A_{i,j} \le 10^9

Sample Input 1

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

Sample Output 1

9
16
23
30
36
41
45
48
52
53

For k=4, it is optimal to catch fish in, for example, (3,1),(4,1),(4,2),(4,5).

To catch fish in these squares, you can move as, for example, (1,1) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (4,1) \rightarrow (4,2) \rightarrow (4,3) \rightarrow (4,4) \rightarrow (4,5) \rightarrow (5,5) \rightarrow (5,6).

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have N points in a two-dimensional plane; the i-th point is (X_i,Y_i). There can be multiple points at the same coordinates. Your task is to choose a point P(p, C) on the line y=C to minimize the cost defined as follows:

• (Cost) = \displaystyle \sum_{i=1}^{N} \bigl((p-X_i)^2+(C-Y_i)^2\bigr)

Print the minimized cost.

Constraints

• All values in input are integers.
• 1 \le N \le 2 \times 10^5
• |C| \le 10^5
• |X_i|,|Y_i| \le 10^5 (1 \le i \le N)

Sample Input 1

3 2
3 0
3 1
3 3

Sample Output 1

6.000000000000000

By choosing (3,2) as P, we can achieve the minimum cost of 6.

Sample Input 2

2 100000
-100000 100000
-100000 100000

Sample Output 2

0.000000000000000

There can be multiple points at the same position.

Sample Input 3

13 -2
3 -6
-4 7
-8 -8
2 9
1 -3
0 4
-6 6
7 0
1 0
-9 7
6 -1
-7 -2
5 6

Sample Output 3

873.769230769230717

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

A convenient store Lun-Lun-Mart currently sells N products. The i-th product has a price of P_i yen and a utility of Q_i points. Also, the store is holding the following campaign:

• For each 100 yen spent, one gift voucher worth 20 yen is awarded. (A fraction less than 100 yen is discarded.)

You have 10^{100} yen. Now, you will choose some (possibly none) of the products sold and buy them. You cannot buy the same product multiple times.
Let us define the score of purchase S as S = T - Q + R, where Q is the total price of products you buy, T is the total utility of products you buy, and R is the total value of vouchers you receive.
Find the maximum possible value of S.

Constraints

• All values in input are integers.
• 1 \le N \le 10^5
• 1 \le P_i,U_i \le 10^4 (1 \le i \le N)

Sample Input 1

3
50 40
30 29
60 55

Sample Output 1

5

For example, if you buy the 1-st and 3-rd products, the total price is 110 yen, the total utility is 95 points, and the total value of vouchers you receive is 20 yen, for the score of 95 - 110 + 20 = 5.
It is impossible to achieve a greater score.

Sample Input 2

1
652 175

Sample Output 2

0

It may be optimal to buy no products.

Sample Input 3

10
859 346
669 705
344 425
693 747
24 808
462 344
930 67
878 35
906 253
531 832

Sample Output 3

1696

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

In some city, there are N towers called Tower 1 through Tower N and M traffic circles called Traffic Circle 1 through Traffic Circle M.
The town has the shape of a circle with a radius of 10^9 meters. Let (x, y) represent the point that is x meters east and y meters north of the center of the circle.
Tower i is at (\mathrm{PX}_i, \mathrm{PY}_i).
Traffic Circle i has the shape of a circle with a radius of R_i meters centered at (\mathrm{CX}_i, \mathrm{CY}_i) (not including the interior).
In this city, Takahashi will build some number of roads, each in the shape of a line segment, to satisfy the following conditions:

• Each endpoint of every road is a point at which one of the N towers stands or on one of the M traffic circles.
• It is possible to travel between every pair of towers in the following manner:
  • if you are now on some traffic circle, you can get to anywhere on that traffic circle;
  • if you are now at an endpoint of some road, you can get to the other endpoint of that road (but not to intermediate points);
  • no other type of movement is allowed.

Find the minimum possible total length of the roads built.

Constraints

• 2 \le N \le 50
• 1 \le M \le 8
• 0 \le \mathrm{PX}_i \le 1000
• 0 \le \mathrm{PY}_i \le 1000
• (\mathrm{PX}_i, \mathrm{PY}_i) \neq (\mathrm{PX}_j, \mathrm{PY}_j) for i \neq j
• 0 \le \mathrm{CX}_i \le 1000
• 0 \le \mathrm{CY}_i \le 1000
• 1 \le R_i \le 1000
• (\mathrm{CX}_i, \mathrm{CY}_i, R_i) \neq (\mathrm{CX}_j, \mathrm{CY}_j, R_j) for i \neq j
• All values in input are integers.

Sample Input 1

2 1
0 0
6 0
3 0 2

Sample Output 1

2.00000000000

The towers and traffic circles are in the following positions:

We can satisfy the conditions by, for example, building the following two roads:

• a road in the shape of a line segment connecting (0, 0) and (1, 0);
• a road in the shape of a line segment connecting (5, 0) and (6, 0).

Here, the total length of the roads built is 2, which is the minimum possible sum.

Sample Input 2

2 2
4 2
0 1
0 0 2
0 1 4

Sample Output 2

2.12310562562

The towers and traffic circles are in the following positions:

It is optimal to build the following three roads:

• a road connecting (0, 1) and (0, 2);
• a road connecting (0, -2) and (0, -3);
• a road connecting (\frac{16 \sqrt{17}}{17}, 1 + \frac{4 \sqrt{17}}{17}) and (4, 2).

Sample Input 3

3 4
9 2
5 20
0 21
0 0 2
0 0 10
16 0 10
10 15 3

Sample Output 3

13.10603728957

The towers and traffic circles are in the following positions:

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a sequence of length N: A = (A_1, A_2, \dots, A_N).

You will be given Q queries, which should be processed in the order they are given. In each query, given integers l, r, and x, do as follows:

• change each of the elements A_l, A_{l+1}, \dots, A_r to x;
• then, report the number of pairs of integers (i, j) such that 1 \le i < j \le N and A_i = A_j.

Constraints

• All values in input are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i \le 10^9 (1 \le i \le N)
• For every query, the following holds:
  • 1 \le l \le r \le N
  • 1 \le x \le 10^9

Sample Input 1

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

Sample Output 1

6
4
5
9
28
16

• Initially, we have A=(3,1,4,1,5,9,2,6).
• The 1-st query makes A (5,5,5,1,5,9,2,6). The response to this query should be 6.
• The 2-nd query makes A (5,1,1,1,5,9,2,6). The response to this query should be 4.
• The 3-rd query makes A (5,1,1,1,5,9,9,6). The response to this query should be 5.
• The 4-th query makes A (5,1,1,1,2,2,2,2). The response to this query should be 9.
• The 5-th query makes A (1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000). The response to this query should be 28.
• The 6-th query makes A (1000000000,999999999,999999999,999999999,999999999,999999999,999999999,1000000000). The response to this query should be 16.

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have N kinds of activities: Activity 1, 2, \dots N. You will choose one or more from these activities and do them in the order you like. The same activity cannot be done multiple times.

Your current stamina is H. Doing activity i gets you a_i \times{}(stamina) points and decreases your stamina by b_i. (It is allowed to do an activity that makes your stamina less than 0.) Find the maximum total number of points you can get.

Constraints

• All values in input are integers.
• 1 ≤ N ≤ 100
• 1 ≤ H ≤ 10^5
• 1 ≤ a_i, b_i ≤ 10^5

Sample Input 1

4 6
4 1
3 2
2 3
1 4

Sample Output 1

45

One way to get a total of 45 points is as follows:

• Your initial stamina is 6.
• Do Activity 1. You get 4 \times 6 = 24 points and your stamina becomes 6 - 1 = 5.
• Do Activity 2. You get 3 \times 5 = 15 points and your stamina becomes 5 - 2 = 3.
• Do Activity 3. You get 2 \times 3 = 6 points and your stamina becomes 3 - 3 = 0.

Sample Input 2

4 6
1 1
2 2
3 3
4 4

Sample Output 2

30

Sample Input 3

16 100
18 17
5 18
7 2
5 8
6 2
16 16
2 18
13 17
18 10
11 10
17 8
1 2
20 7
4 11
7 15
2 1

Sample Output 3

9282

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You are given an simple connected undirected graph, where M ≤ N + 10. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M. Edge i connects Vertex a_i and Vertex b_i. The length of every edge is 1.

Process Q queries in order. The i-th query is as follows:

• given integers u_i and v_i, find the shortest distance between Vertex u_i and Vertex v_i.

Constraints

• All values in input are integers.
• 2 ≤ N ≤ 10^5
• N - 1 ≤ M ≤ N + 10
• 1 ≤ a_i < b_i ≤ N
• (a_i, b_i) ≠ (a_j, b_j) for i ≠ j
• The given graph is connected.
• 1 ≤ Q ≤ 10^4
• 1 ≤ u_i < v_i ≤ N

Sample Input 1

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

Sample Output 1

2
4
1

The given graph is as follows:

Thus,

• the shortest distance between Vertex 4 and Vertex 6 is 2;
• the shortest distance between Vertex 1 and Vertex 5 is 4;
• the shortest distance between Vertex 1 and Vertex 2 is 1.

Sample Input 2

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

Sample Output 2

3
3
2
4
1
1
1
4

Sample Input 3

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

Sample Output 3

2
4
1
3
5
2