19742번 - Interesting excursion 스페셜 저지다국어

Flatland has $n$ cities, connected by $m$ one-directional roads.

Tourist company plans to develop a scenic cyclic tour along the roads of Flatland. This tour must start and finish at the same city, visiting some intermediate cities and traveling along some of the roads in their direction. The tour can visit some city multiple times, but it may not use the same road more than once.

Each road is characterized by the type of its landscape, which is the number from $1$ to $m$. To make the tour really magnificent, every two adjacent roads in the tour must have different landscape types. This also should be true for the first and the last road in the tour, so that you start to travel from any city of the tour.

Help the company to find the tour satisfying these conditions, or report that no such tour exists.  

Input contains multiple test cases. First line contains integer $T$ ($1 \le T \le 10^5$) --- the number of test cases.

First line of each test case's description contains two integers  $n$ and $m$ ($2 \le n, m \le 2 \cdot 10^5$) --- number of cities and roads. Each of next $m$ lines contain three integers $u_i$ $v_i$ $c_i$, meaning that $i$-th road starts at city $u_i$, ends at city $v_i$ and has landscape type $c_i$ ($1 \le u_i, v_i \le n$, $1 \le c_i \le m$, $u_i \neq v_i$).

Sum of all $n$ in all test cases does not exceed $2 \cdot 10^5$. Sum of all $m$ in all test cases does not exceed $2 \cdot 10^5$.

Output the answer of each test case.

If the desired tour does not exist, output the only number <<$-1$>>. Otherwise, print number k $2 \le k \le m$ --- the length of the tour. In next line print $k$ numbers $e_1, e_2, \ldots, e_k$ --- numbers of roads in the tour. All numbers $e_i$ must be different. If there are multiple possible tours, output any of them.