Perfect Matching solution codeforces- You are given a tree consisting of nn vertices (numbered from 11 to nn) and n−1n−1 edges (numbered from 11 to n−1n−1). Initially, all vertices except vertex 11 are inactive. You have to process queries of three types:

Perfect Matching solution codeforces

You are given a tree consisting of nn vertices (numbered from 11 to nn) and n−1n−1 edges (numbered from 11 to n−1n−1). Initially, all vertices except vertex 11 are inactive.

You have to process queries of three types:

  • 11 vv — activate the vertex vv. It is guaranteed that the vertex vv is inactive before this query, and one of its neighbors is active. After activating the vertex, you have to choose a subset of edges of the tree such that each active vertex is incident to exactly one chosen edge, and each inactive vertex is not incident to any of the chosen edges — in other words, this subset should represent a perfect matching on the active part of the tree. If any such subset of edges exists, print the sum of indices of edges in it; otherwise, print 00.
  • 22 — queries of this type will be asked only right after a query of type 11, and there will be at most 1010 such queries. If your answer to the previous query was 00, simply print 00; otherwise, print the subset of edges for the previous query as follows: first, print the number of edges in the subset, then print the indices of the chosen edges in ascending order. The sum of indices should be equal to your answer to the previous query.
  • 33 — terminate the program.

Note that you should solve the problem in online mode. It means that you can’t read the whole input at once. You can read each query only after writing the answer for the last query. Use functions fflush in C++ and BufferedWriter.flush in Java languages after each writing in your program.

Input Perfect Matching solution codeforces

The first line contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of vertices of the tree.

Then n−1n−1 lines follow. The ii-th line contains two integers uiui and vivi (1≤ui,vi≤n1≤ui,vi≤n; ui≠viui≠vi) — the endpoints of the ii-th edge. These edges form a tree.

Then the queries follow in the format described in the statement, one line per query. There will be at least 22 and at most n+10n+10 queries. The last query (and only the last one) will be of type 33. Note that you can read the ii-th query only if you have already given the answer for the query i−1i−1 (except for i=1i=1).

If your answer for one of the queries is incorrect and the judging program recognizes it, instead of the next query, you may receive the integer 00 on a separate line. After receiving it, your program should terminate gracefully, and you will receive “Wrong Answer” verdict. If your program doesn’t terminate, your solution may receive some other verdict, like “Time Limit Exceeded”, “Idleness Limit Exceeded”, etc. Note that the fact that your solution doesn’t receive the integer 00, it does not mean that all your answers are correct, some of them will be checked only after your program is terminated.

Output

For each query of type 11 or 22, print the answer on a separate line as described in the statement. Don’t forget to flush the output.

Example Perfect Matching solution codeforces

input

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

output Perfect Matching solution codeforces

Copy
1
1 1
0
0
4
2 1 3
0
0
0

Leave a Comment

Your email address will not be published.