The Parliament wants to adopt a very important law, but for this they have
to get information about the cities of the country. Consequently, every mayor
is asked for information about the city he's managing. The files received from
the mayors are not at all easy to comprehend, so they have to be written so
that everyone can understand them.
We know that every city consists of several quarters of houses. The
quarters are limited by roads surrounding them, but there are no roads inside
any of the quarters. There are for sure two types of rings (belts) in every
city:
- each quarter's ring, made up of the roads surrounding it.
- the city's ring, consisting of the roads surrounding all the quarters. Of
course, this one includes the roads that are also parts of the rings of the
city-limit (boundary) quarters.
Remarks:
- the roads are straight.
- two or more roads can form a crossing.
- between two crossings there can be at least two roads (roads succeeding one
another), having no common road.
The Parliament wants to find out how many quarters exist in each city and
which are the rings of the city and of its quarters.
Input Data:
The input file is called INPUT.TXT and has the following
form:
n m - n is the number of the crossings and m, the number
of roads
x1 y1 - the coordinates of the first crossing
.......
xn yn - the coordinates of the crossing no. n
q1 w1 - road between the crossings q1 and w1
........
qm wm - road between the crossings qm and wm
Output Data:
The output goes to the text file OUTPUT.TXT, having the
following form:
- in the first line, the number, C, of that city's quarters;
- in the following C+1 lines the quarters' and city's rings will be
written and specified in the order number of the crossings they (the rings)
include, written in the order obtained when the ring is run.
The numbers of the crossroads will be separated by a space and the last
crossing in the ring will also be the first.
Limits:
All the numbers that appear in the problem are natural numbers, smaller
than 5001.
Example 1:
INPUT.TXT
6 7
1 1
2 1
1 2
2 2
1 3
2 3
1 2
3 4
5 6
1 3
3 5
2 4
4 6
OUTPUT.TXT
2
1 2 4 6 5 3 1
1 3 4 2 1
3 5 6 4 3
Example 2:
INPUT.TXT
4 4
1 1
2 1
1 2
2 2
1 2
3 4
1 3
2 4
OUTPUT.TXT
1
1 2 4 3 1
1 2 4 3 1
Execution time:
1 second/test on a Pentium/166 MHz.