Dany jest graf nieskierowany o $n$ wierzchołkach i $m$ krawędziach. Należy pomalować każdą krawędź jednym z $m$ kolorów w taki sposób, aby dla każdego wierzchołka $u$ oraz każdego koloru $c$, co najwyżej 2 krawędzie incydentne z wierzchołkiem $u$ były pomalowane kolorem $c$.

Formalnie, dla wszystkich liczb całkowitych $1 \le u \le n$, musi zostać spełniony następujący warunek: niech $d_u$ będzie liczbą krawędzi incydentnych z wierzchołkiem $u$, niech $e_{u,1}, e_{u,2}, \dots, e_{u,d_u}$ będą tymi krawędziami, a $w(e)$ będzie kolorem krawędzi $e$ (kolory są ponumerowane od $1$ do $m$). Wówczas dla wszystkich liczb całkowitych $1 \le c \le m$, kolor $c$ występuje co najwyżej dwa razy w ciągu $w(e_{u,1}), w(e_{u,2}), \dots, w(e_{u,d_u})$.

Niech $f_u$ oznacza liczbę różnych kolorów wszystkich krawędzi incydentnych z wierzchołkiem $u$. Znajdź sposób pomalowania krawędzi tak, aby zminimalizować $\sum_{u=1}^{n} f_u$.

Wejście

Wejście zawiera wiele zestawów danych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$) określającą liczbę zestawów danych. Dla każdego zestawu danych:

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($2 \le n \le 2 \times 10^5$, $1 \le m \le \min(\frac{n(n-1)}{2}, 2 \times 10^5)$), określające liczbę wierzchołków oraz liczbę krawędzi w grafie.

W kolejnych $m$ liniach, $i$-ta linia zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n$), oznaczające, że $i$-ta krawędź łączy wierzchołki $u_i$ oraz $v_i$.

Gwarantuje się, że w grafie nie ma pętli własnych ani krawędzi wielokrotnych. Jednakże dany graf może nie być spójny. Gwarantuje się również, że suma $n$ oraz suma $m$ dla wszystkich zestawów danych nie przekroczy $2 \times 10^5$.

Wyjście

Dla każdego zestawu danych wypisz jedną linię zawierającą $m$ liczb całkowitych $w_1, w_2, \dots, w_m$ ($1 \le w_i \le m$) oddzielonych spacjami, gdzie $w_i$ jest kolorem $i$-tej krawędzi.

Jeśli istnieje wiele poprawnych rozwiązań, możesz wypisać dowolne z nich.

Przykład

Wejście 1

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

Wyjście 1

2 2 3 3 2 3 6
2 1