Problem Statement

There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:

• M \geq 2
• The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
• The edge from vertex B_M to vertex B_1 exists.
• If i \neq j, then B_i \neq B_j.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le N
• A_i \neq i

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.

Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input:

Problem Statement

Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq a_i,b_i \leq 10^9
• All input values are integers.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.

Thus, the answer is 3.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Sample Output 3

492686569

Problem Statement

Among the sequences P that are permutations of (1, 2, \dots, N) and satisfy the condition below, find the lexicographically smallest sequence.

• For each i = 1, \dots, M, A_i appears earlier than B_i in P.

If there is no such P, print -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• All values in input are integers.

Sample Input 1

4 3
2 1
3 4
2 4

Sample Output 1

2 1 3 4

The following five permutations P satisfy the condition: (2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1). The lexicographically smallest among them is (2, 1, 3, 4).

Sample Input 2

2 3
1 2
1 2
2 1

Sample Output 2

-1

No permutations P satisfy the condition.

Problem Statement

The Kingdom of AtCoder has N cities called City 1,2,\ldots,N and M roads called Road 1,2,\ldots,M.
Road i connects Cities A_i and B_i bidirectionally and has a length of C_i.
One can travel between any two cities using some roads.

Under financial difficulties, the kingdom has decided to maintain only N-1 roads so that one can still travel between any two cities using those roads and abandon the rest.

Let d_i be the total length of the roads one must use when going from City 1 to City i using only maintained roads. Print a choice of roads to maintain that minimizes d_2+d_3+\ldots+d_N.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq A_i < B_i \leq N
• (A_i,B_i)\neq(A_j,B_j) if i\neq j.
• 1\leq C_i \leq 10^9
• One can travel between any two cities using some roads.
• All values in input are integers.

Sample Input 1

3 3
1 2 1
2 3 2
1 3 10

Sample Output 1

1 2

Here are the possible choices of roads to maintain and the corresponding values of d_i.

• Maintain Road 1 and 2: d_2=1, d_3=3.
• Maintain Road 1 and 3: d_2=1, d_3=10.
• Maintain Road 2 and 3: d_2=12, d_3=10.

Thus, maintaining Road 1 and 2 minimizes d_2+d_3.

Sample Input 2

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

Sample Output 2

3 1 2

Problem Statement

There are N balls arranged from left to right. The color of the i-th ball from the left is Color C_i, and an integer X_i is written on it.

Takahashi wants to rearrange the balls so that the integers written on the balls are non-decreasing from left to right. In other words, his objective is to reach a situation where, for every 1\leq i\leq N-1, the number written on the (i+1)-th ball from the left is greater than or equal to the number written on the i-th ball from the left.

For this, Takahashi can repeat the following operation any number of times (possibly zero):

Choose an integer i such that 1\leq i\leq N-1.
If the colors of the i-th and (i+1)-th balls from the left are different, pay a cost of 1. (No cost is incurred if the colors are the same).
Swap the i-th and (i+1)-th balls from the left.

Find the minimum total cost Takahashi needs to pay to achieve his objective.

Constraints

• 2 \leq N \leq 3\times 10^5
• 1\leq C_i\leq N
• 1\leq X_i\leq N
• All values in input are integers.

Sample Input 1

5
1 5 2 2 1
3 2 1 2 1

Sample Output 1

6

Let us represent a ball as (Color, Integer). The initial situation is (1,3), (5,2), (2,1), (2,2), (1,1). Here is a possible sequence of operations for Takahashi:

• Swap the 1-st ball (Color 1) and 2-nd ball (Color 5). Now the balls are arranged in the order (5,2), (1,3), (2,1), (2,2), (1,1).
• Swap the 2-nd ball (Color 1) and 3-rd ball (Color 2). Now the balls are arranged in the order (5,2), (2,1), (1,3), (2,2), (1,1).
• Swap the 3-rd ball (Color 1) and 4-th ball (Color 2). Now the balls are in the order (5,2), (2,1), (2,2), (1,3), (1,1).
• Swap the 4-th ball (Color 1) and 5-th ball (Color 1). Now the balls are in the order (5,2), (2,1), (2,2), (1,1), (1,3).
• Swap the 3-rd ball (Color 2) and 4-th ball (Color 1). Now the balls are in the order(5,2), (2,1), (1,1), (2,2), (1,3).
• Swap the 1-st ball (Color 5) and 2-nd ball (Color 2). Now the balls are in the order (2,1), (5,2), (1,1), (2,2), (1,3).
• Swap the 2-nd ball (Color 5) and 3-rd ball (Color 1). Now the balls are in the order (2,1), (1,1), (5,2), (2,2), (1,3).

After the last operation, the numbers written on the balls are 1,1,2,2,3 from left to right, which achieves Takahashi's objective.

The 1-st, 2-nd, 3-rd, 5-th, 6-th, and 7-th operations incur a cost of 1 each, for a total of 6, which is the minimum. Note that the 4-th operation does not incur a cost since the balls are both in Color 1.

Sample Input 2

3
1 1 1
3 2 1

Sample Output 2

0

All balls are in the same color, so no cost is incurred in swapping balls.

Sample Input 3

3
3 1 2
1 1 2

Sample Output 3

0

Takahashi's objective is already achieved without any operation.