405862: GYM102136 D Badroadville mayoral election

Today people discuss elections at all cross-roads. Scandals, intrigues, investigations, disclosures. In our town called Badroadville it's also time to elect a mayor. And in an attempt to avoid the usual infighting, we decided to change the concept radically: the winner will be determined by deed, not by word. And a deed will be very important — it will be road construction.

There are several districts in Badroadville, where N houses are located. Houses are connected by M bidirectional roads. There are not many roads, as always. The roads between the houses are not duplicated, and there are no roads looping and leading to the same house. There is always at least one path between any pair of houses in a district (by the way, a district can consist of the only house). But there are no roads from one district to another, so unlucky town residents have to wade knee-deep through the mud.

The candidates running to be the next mayor will build one road between two houses in turns, and the one, who first turns the city into one big and happy district, will become a new mayor of Badroadville.

We suggest you take part in the election race with our candidate and prove that you are ready to rule the town and bring it to the better tomorrow!

As a welcome guest, you can choose who will be the first to start the construction of roads.

The first line contains two integers N and M — the numbers of houses and roads in the town, respectively.

The next M lines describe roads as U_i V_i — the numbers of houses connected by this road.

Once you've received the current Badroadville scheme of roads, you need to print one of the numbers: "1" or "2" depending on your wish to start the election race the first or the second, respectively.

Now, if it's your turn, you need to print two integers U V — the numbers of houses that you are going to connect by the road. If it is your opponent's turn now, you get two integers U V   — the numbers of houses that your opponent connected by the road.

You must correctly finish the election race when there remains just one district in the town or when the opponent send you two zeroes "0 0".

Please don't forget to output a newline character and to clear a buffer. For example, you may use fflush(stdout) in C++, System.out.flush() in Java, and flush(output) in Pascal.

4 0
3 4

1
1 2
1 3

5 1
3 5
2 3
0 0

1
1 2
1 5