I. Help the Aztecs
time limit per test
0.6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Aztecs were a civilization that emerged around 1300 in regions that now belong to Mexico. The Aztec empire had city-states with elaborate urban planning, an expressive cultural production, and influence in different spheres of Mexican modern society, like language and cuisine.

The economy was centered on agriculture, especially corn and beans. Hence, we can consider the empire as being divided into $$$n$$$ plantation fields. Two fields may be connected by a road. We know the empire had $$$m$$$ roads in total.

Imagine now that you became the Aztec emperor, therefore you need to control the empire's economy and your people's happiness. Your counselors told you that if a road has one endpoint at a been field and another at a corn field, the population considers that road as being good because it shows the diversity of the agriculture. During your government $$$q$$$ events will happen, these events can be of two types. Events of type 1 happen when the rain god, Tlaloc, is angry with the empire and flood one of the fields together with all roads that reached the flooded field. After events of type 1 the destroyed field and roads never come back to existence. Events of type 2 happen when Tlaloc is happy and provides good weather for plantations, in this case, you should decide which fields will cultivate corn, and consequently, all others will cultivate beans. For your population to be satisfied is necessary that at least half of the existing empire's roads are good. Now you must play your role as the emperor to guarantee the happiness of your population, and that the empire can keep prospering!

Input

The first line has three integers $$$1 \leq n \leq 2500$$$, $$$0 \leq m \leq 2 \times 10^5 $$$ and $$$1 \leq q \leq 5000$$$, which represent the number of fields in the empire, the total number of roads at the beginning, and the number of events that will happen.

The next $$$m$$$ lines have two integers $$$u$$$ and $$$v$$$, representing that there is a road between fields $$$u$$$ and $$$v$$$. Between any pair of fields, there is at most one road connecting them.

The next $$$q$$$ lines can be of two types, and represent the events that will happen. The line can have the number 1 followed by a field $$$v$$$, this means that an event of type 1 happened at field $$$v$$$. Note that an event of type 1 cannot happen twice in the same fields. In the other case, the line will have only the number 2, indicating that an event of type 2 happened.

Output

For each event of type 2, you should print a line. This line should have an integer $$$k$$$, representing how many fields will cultivate corn, followed by $$$k$$$ integers representing which are those fields. The number of good roads choosing these plantations should be at least half of the remaining roads in the empire. It can be proven that an answer always exists. If there are multiple answers, you can print any of them.

Examples
Input
5 5 3
1 2
2 3
3 4
4 5
1 5
2
1 1
2
Output
2 1 3
2 2 4
Input
6 9 4
4 1
1 5
1 6
4 2
4 3
5 3
5 2
6 3
6 2
1 1
1 4
2
2
Output
1 2
2 2 3
Note

In the first test case, if in the first event, you choose fields 1 and 3 to plant corn, and consequently fields 2, 4, and 5 to plant beans, then 4 out of 5 roads will be good. After field 1 is flooded, if you choose fields 2 and 4 to plant corn, then 3 out of 3 roads will be good.