CF1070I.Privatization of Roads in Berland

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.

伯兰德有 $n$ 座城市和 $m$ 条双向道路，每条道路连接两个不同的城市。

最近，伯兰德政府做出了一个艰难的决定：将道路的所有权转让给私营公司。伯兰德全国共有 $100500$ 家私营公司，编号为整数 $1$ 到 $100500$。私有化后，每条道路必须且仅属于一家公司。

反垄断委员会要求：私有化后，每家公司最多只能拥有两条道路。伯兰德的城市规划者也提出了意见：每个城市所邻接的道路，其所属公司种类数至多为 $k$。

请帮助政府将道路分配给各公司，使得上述两个条件均被满足。即：每家公司获得的道路数不超过两条，且每个城市邻接的道路所属公司种类数不超过 $k$。

Input contains one or several test cases. The first line contains an integer $t$ ($1 \le t \le 300$) — the number of test cases in the input. Solve test cases separately, test cases are completely independent and do not affect each other.

The following lines describe the test cases. Each case starts with a line consisting of three space-separated integers $n$, $m$ and $k$ ($2 \le n \le 600$, $1 \le m \le 600$, $1 \le k \le n - 1$) — the number of cities, the number of roads and the maximum diversity of the roads adjacent to a city.

Then $m$ lines follow, each having a pair of space-separated integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$; $a_i \ne b_i$). It means that the $i$-th road connects cities $a_i$ and $b_i$. All roads are two-way. There is at most one road between a pair of the cities.

The sum of $n$ values for all test cases doesn't exceed $600$. The sum of $m$ values for all test cases doesn't exceed $600$.

输入包含一个或多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 300$），表示输入中测试用例的数量。请分别求解各测试用例，各测试用例完全独立，互不影响。

接下来的若干行描述各个测试用例。每个测试用例以一行开始，该行包含三个以空格分隔的整数 $n$、$m$ 和 $k$（$2 \le n \le 600$，$1 \le m \le 600$，$1 \le k \le n - 1$），分别表示城市的数量、道路的数量，以及每个城市所连道路的最大多样性（即与该城市相连的道路种类数上限）。

随后是 $m$ 行，每行包含一对以空格分隔的整数 $a_i$、$b_i$（$1 \le a_i, b_i \le n$；$a_i \ne b_i$），表示第 $i$ 条道路连接城市 $a_i$ 和 $b_i$。所有道路均为双向道路，且任意两个城市之间至多存在一条道路。

所有测试用例的 $n$ 值之和不超过 $600$；所有测试用例的 $m$ 值之和不超过 $600$。

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$.

输出 $t$ 行：第 $i$ 行应包含第 $i$ 个测试用例的答案。对于每个测试用例，输出一串由空格分隔的整数 $c_1, c_2, \dots, c_m$，其中 $c_i$（$1 \le c_i \le 100500$）表示你所规划的第 $i$ 条道路所属的公司。若存在多个解，输出任意一个即可。若某个测试用例无解，则输出 $c_1=c_2=\ldots=c_m=0$。