Дан неориентированный граф с $n$ вершинами и $m$ ребрами. Вам необходимо раскрасить каждое ребро в один из $m$ цветов так, чтобы для любой вершины $u$ и любого цвета $c$ не более 2 ребер, инцидентных вершине $u$, были окрашены в цвет $c$.

Более формально, для всех целых чисел $1 \le u \le n$ должно выполняться следующее ограничение: пусть $d_u$ — количество ребер, инцидентных вершине $u$, пусть $e_{u,1}, e_{u,2}, \dots, e_{u,d_u}$ — эти ребра, а $w(e)$ — цвет ребра $e$ (цвета пронумерованы от 1 до $m$). Тогда для всех целых чисел $1 \le c \le m$ цвет $c$ встречается не более двух раз в последовательности $w(e_{u,1}), w(e_{u,2}), \dots, w(e_{u,d_u})$.

Пусть $f_u$ — количество различных цветов на всех ребрах, инцидентных вершине $u$. Найдите способ раскрасить ребра так, чтобы минимизировать $\sum_{u=1}^n f_u$.

Входные данные

Входные данные содержат несколько тестовых случаев. В первой строке находится целое число $T$ ($1 \le T \le 10^4$), количество тестовых случаев. Для каждого тестового случая:

Первая строка содержит два целых числа $n$ и $m$ ($2 \le n \le 2 \times 10^5$, $1 \le m \le \min(\frac{n(n-1)}{2}, 2 \times 10^5)$), количество вершин и количество ребер в графе.

В следующих $m$ строках $i$-я строка содержит два целых числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$), означающих, что $i$-е ребро соединяет вершины $u_i$ и $v_i$.

Гарантируется, что в графе нет петель и кратных ребер. Однако граф может быть несвязным. Также гарантируется, что сумма $n$ и сумма $m$ по всем тестовым случаям не превышают $2 \times 10^5$.

Выходные данные

Для каждого тестового случая выведите одну строку, содержащую $m$ целых чисел $w_1, w_2, \dots, w_m$ ($1 \le w_i \le m$), разделенных пробелом, где $w_i$ — цвет, в который окрашено $i$-е ребро.

Если существует несколько подходящих вариантов раскраски, вы можете вывести любой из них.

Примеры

Пример 1

2
5 7
1 5
2 5
3 5
4 5
1 2
3 4
3 1
4 2
1 2
3 4

Пример 2

2 2 3 3 2 3 6
2 1