413. Berland Division
Time limit per test: 0.25
Memory limit: 65536
It is widely known that Berland consists of an even number of cities connected by bidirectional roads.
It is possible to travel between every pair of cities using the roads. There is no such pair of
cities which is connected by more than one road, and there is no road wich connects a city to itself.
Due to the raised conflicts Berland can not exist as a single country. People don't want to share
one roof anymore. It was decided to create the Berland Union and divide the Berland into
several countries. There were two basic conditions. Firstly, every country must consist of not less than
two cities, because no city can survive without help of other cities. Secondly, there must be exactly one
path between each pair of cities from one country, which passes through the cities of this country.
Help to create the division plan which fulfills these two requirements. Note that you don't need to
minimize the number of countries.
Input contains several test cases. The number of test cases tst
(1 ≤ tst
≤ 50) is given on the first line of the input.
Each test decription consists of a line with two integers n
(2 ≤ n
≤ 100, 1 ≤ m
≤ 1000, n
— even) —
number of cities and roads correspondingly. Each of the following m
lines contains two integer numbers
(1 ≤ a
), describing the road between a
. The total number of cities in all of the cases
doesn't exceed 100, and the total number of roads doesn't exceed 1000.
For each test case output n
numbers on a separate line: i
-th number should be the number of country which i
-th city belongs to.
Countries must be numerated from 1 to k
, where k
is the number of countries in your plan. If there are several solutions,
output any of them.
1 1 1 1
1 2 2 1