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 and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000, n — even) — number of cities and roads correspondingly. Each of the following m lines contains two integer numbers a and b (1 ≤ a < b ≤ n), describing the road between a and b. 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.

sample input	sample output
2 4 3 1 2 2 3 1 4 4 4 1 2 2 3 1 4 1 3	1 1 1 1 1 2 2 1