Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

• Choose two same-colored socks that are not paired yet, and pair them.

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2

You can do the operation twice as follows.

• Choose two socks with the color 1 and pair them.
• Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
  • 1 \le X_i \le 9 for all integers 1 \le i \le N;
  • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

• N is an integer.
• 2 \le N \le 10^6

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

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

Given is an undirected graph with N vertices and M edges.
Edge i connects Vertices A_i and B_i.

We will erase Vertices 1, 2, \ldots, N one by one.
Here, erasing Vertex i means deleting Vertex i and all edges incident to Vertex i from the graph.

For each i=1, 2, \ldots, N, how many connected components does the graph have when vertices up to Vertex i are deleted?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )
• 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 7
1 2
1 4
1 5
2 4
2 3
3 5
3 6

Sample Output 1

1
2
3
2
1
0

The figure above shows the transition of the graph.

Sample Input 2

8 7
7 8
3 4
5 6
5 7
5 8
6 7
6 8

Sample Output 2

3
2
2
1
1
1
1
0

The graph may be disconnected from the beginning.

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.