Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is simple.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

2

One way to remove cycles from the graph is to delete the two edges between vertex 1 and vertex 2 and between vertex 4 and vertex 5.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print 2.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

0

Sample Input 3

5 3
1 2
1 3
2 3

Sample Output 3

1

Problem Statement

Given an integer N, solve the following problem.

Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.

Constraints

• N is an integer.
• 1 \le N < 10^{18}

Sample Input 1

16

Sample Output 1

73

• For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
  • Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
• For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
  • Thus, we have f(10)=1,f(11)=2,...,f(16)=7.

The final answer is 73.

Sample Input 2

238

Sample Output 2

13870

Sample Input 3

999999999999999999

Sample Output 3

762062362

Be sure to find the sum modulo 998244353.

Problem Statement

This is an interactive task (where your program and the judge interact via Standard Input and Output).

You are given an integer N and an odd number K.
The judge has a hidden length-N sequence A = (A_1, A_2, \dots, A_N) consisting of 0 and 1.

While you cannot directly access the elements of sequence A, you are allowed to ask the judge the following query at most N times.

• Choose distinct integers x_1, x_2, \dots, and x_K between 1 and N, inclusive, to ask the parity of A_{x_1} + A_{x_2} + \dots + A_{x_K}.

Determine (A_1, A_2, \dots, A_N) by at most N queries, and print the answer.
Here, the judge is adaptive. In other words, the judge may modify the contents of A as long as it is consistent with the responses to the past queries.
Therefore, your program is considered correct if the output satisfies the following condition, and incorrect otherwise:

• your program prints a sequence consistent with the responses to the queries so far, and that is the only such sequence.

Constraints

• 1 \leq K \lt N \leq 1000
• K is odd.
• A_i is 0 or 1.

Input and Output

This is an interactive task (where your program and the judge interact via Standard Input and Output).

First of all, receive N and K from Standard Input.

N K

Then, repeat asking queries until you can uniquely determine (A_1, A_2, \dots, A_N).
Each query should be printed to Standard Output in the following format, where x_1, x_2, \dots, and x_K are K distinct integers between 1 and N, inclusive.

? x_1 x_2 \dots x_K

The response to the query is given from Standard Input in the following format.

T

Here, T denotes the response to the query.

• T is 0 when A_{x_1} + A_{x_2} + \dots + A_{x_K} is even, and
• T is 1 when A_{x_1} + A_{x_2} + \dots + A_{x_K} is odd.

However, if x_1, x_2, \dots and x_K do not satisfy the constraints, or the number of queries exceeds N, then T is -1.

If the judge returns -1, your program is already considered incorrect, so terminate the program immediately.

When you can determine all the elements of A, print those elements in the following format, and terminate the program immediately.

! A_1 A_2 \dots A_N

Notes

• Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.
• The verdict will be indeterminate if there is malformed output during the interaction or your program quits prematurely.
• Terminate the program immediately after printing the answer, or the verdict will be indeterminate.
• The judge for this problem is adaptive. This means that the judge may modify the contents of A as long as it is consistent with the responses to the past queries.

Sample Interaction

In the following interaction, N=5 and K=3. Note that the following output itself will result in WA.
Here, A = (1, 0, 1, 1, 0) is indeed consistent with the responses, but so is (0, 0, 1, 0, 0), so sequence A is not uniquely determined. Thus, this program is considered incorrect.

Problem Statement

A graph with (k+1) vertices and k edges is called a level-k\ (k\geq 2) star if and only if:

• it has a vertex that is connected to each of the other k vertices with an edge, and there are no other edges.

At first, Takahashi had a graph consisting of stars. He repeated the following operation until every pair of vertices in the graph was connected:

• choose two vertices in the graph. Here, the vertices must be disconnected, and their degrees must be both 1. Add an edge that connects the chosen two vertices.

He then arbitrarily assigned an integer from 1 through N to each of the vertices in the graph after the procedure. The resulting graph is a tree; we call it T. T has (N-1) edges, the i-th of which connects u_i and v_i.

Takahashi has now forgotten the number and levels of the stars that he initially had. Find them, given T.

Constraints

• 3\leq N\leq 2\times 10^5
• 1\leq u_i, v_i\leq N
• The given graph is an N-vertex tree obtained by the procedure in the problem statement.
• All values in the input are integers.

Sample Input 1

6
1 2
2 3
3 4
4 5
5 6

Sample Output 1

2 2

Two level-2 stars yield T, as the following figure shows:

Sample Input 2

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

Sample Output 2

2 2 2

Sample Input 3

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

Sample Output 3

2 3 4 7

Problem Statement

There are N cities numbered city 1, city 2, \ldots, and city N.
There are also one-way teleporters that send you to different cities. Whether a teleporter can send you directly from city i (1\leq i\leq N) to another is represented by a length-M string S_i consisting of 0 and 1. Specifically, for 1\leq j\leq N,

• if 1\leq j-i\leq M and the (j-i)-th character of S_i is 1, then a teleporter can send you directly from city i to city j;
• otherwise, it cannot send you directly from city i to city j.

Solve the following problem for k=2,3,\ldots, N-1:

Can you travel from city 1 to city N without visiting city k by repeatedly using a teleporter? If you can, print the minimum number of times you need to use a teleporter; otherwise, print -1.

Constraints

• 3 \leq N \leq 10^5
• 1\leq M\leq 10
• M<N
• S_i is a string of length M consisting of 0 and 1.
• If i+j>N, then the j-th character of S_i is 0.
• N and M are integers.

Sample Input 1

5 2
11
01
11
10
00

Sample Output 1

2 3 2

A teleporter sends you

• from city 1 to cities 2 and 3;
• from city 2 to city 4;
• from city 3 to cities 4 and 5;
• from city 4 to city 5; and
• from city 5 to nowhere.

Therefore, there are three paths to travel from city 1 to city 5:

• path 1 : city 1 \to city 2 \to city 4 \to city 5;
• path 2 : city 1 \to city 3 \to city 4 \to city 5; and
• path 3 : city 1 \to city 3 \to city 5.

Among these paths,

• two paths, path 2 and path 3, do not visit city 2. Among them, path 3 requires the minimum number of teleporter uses (twice).
• Path 1 is the only path without city 3. It requires using a teleporter three times.
• Path 3 is the only path without city 4. It requires using a teleporter twice.

Thus, 2, 3, and 2, separated by spaces, should be printed.

Sample Input 2

6 3
101
001
101
000
100
000

Sample Output 2

-1 3 3 -1

The only path from city 1 to city 6 is city 1 \to city 2 \to city 5 \to city 6.
For k=2,5, there is no way to travel from city 1 to city 6 without visiting city k.
For k=3,4, the path above satisfies the condition; it requires using a teleporter three times.

Thus, -1, 3, 3, and -1, separated by spaces, should be printed.

Note that a teleporter is one-way; a teleporter can send you from city 3 to city 4, but not from city 4 to city 3,
so the following path, for example, is invalid: city 1 \to city 4 \to city 3 \to city 6.