There are \(n\) cities and \(m\) two-way roads in Berland, each road connecting two distinct cities.
Recently the Berland government has made a tough decision to transfer ownership of the roads to private companies. In total, there are \(100500\) private companies in Berland, numbered by integers from \(1\) to \(100500\). After the privatization, every road should belong to exactly one company.
The anti-monopoly committee demands that after the privatization each company can own at most two roads. The urbanists of Berland also stated their opinion: each city should be adjacent to the roads owned by at most \(k\) companies.
Help the government to distribute the roads between the companies so that both conditions are satisfied. That is, each company gets at most two roads, and each city has roads of at most \(k\) distinct companies adjacent to it.
Output
Print \(t\) lines: the \(i\)-th line should contain the answer for the \(i\)-th test case. For a test case, print a sequence of integers \(c_1, c_2, \dots, c_m\) separated by space, where \(c_i\) (\(1 \le c_i \le 100500\)) is the company which owns the \(i\)-th road in your plan. If there are multiple solutions, output any of them. If there is no solution for a test case, print \(c_1=c_2=\ldots=c_m=0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 3 2
1 2
2 3
3 1
4 5 2
1 2
1 3
1 4
2 3
2 4
4 6 2
1 2
1 3
1 4
2 3
2 4
3 4
|
1 2 3
2 1 1 2 3
0 0 0 0 0 0
|