eolymp
bolt
Try our new interface for solving problems
Problems

Интересная экскурсия

Интересная экскурсия

Time limit 4 seconds
Memory limit 512 MiB

Во Флатландии n городов, соединенных m односторонними дорогами.

Туристическая компания планирует разработать живописный циклический маршрут по дорогам Флатландии. Маршрут должен начинаться и заканчиваться в одном и том же городе и проходить по дорогам в их направлении, посещая промежуточные города. Маршрут может посещать один город несколько раз, но должен проходить по каждой дороге не более одного раза.

Каждая дорога характеризуется типом своего пейзажа, который задается числом от 1 до m. Чтобы туристический маршрут был живописным, любые две соседние дороги в этом маршруте должны иметь разный тип пейзажа. Это же требование относится к первой и последней дороге маршрута, чтобы можно было начинать путешествовать, начиная с любого города маршрута.

Помогите компании разработать удовлетворяющий этим критериям маршрут, либо выясните, что сделать это е.

Input data

Входные данные состоят из нескольких тестов. В первой строке находится число T — количество тестов (1 ≤ T ≤ 10^5).

Первая строка описания каждого теста содержит два целых числа n и m — количество городов и дорог (2 ≤ n;m ≤ 2 * 10^5). Следующие m строк содержат по три целых числа и описывают дороги в формате u[i]v[i]c[i] — город, из которого выходит i-я дорога, город, в который она ведет, и тип еёпейзажа (1 ≤ u[i]; v[i] ≤ n; 1 ≤ c[i] ≤ m; u[i] ̸= v[i]).

Сумма n по всем тестам не превосходит 2 * 10^5. Сумма m по всем тестам не превосходит 2 * 10^5.

Output data

Выведите ответ для каждого теста.Если искомого маршрута не существует, следует вывести число «-1». Иначе, выведите число k — длину маршрута (2 ≤ k ≤ m). В следующей строке выведите k чисел e1; e2; : : : ; ek — номера дорог в том порядке, в каком они идут в этом маршруте. Все номера ei должны быть различны. Если подходящих маршрутов несколько, можно вывести любой из них.

Examples

Input example #1
3
5 8
1 4 1
2 4 1
4 5 2
3 2 2
5 3 1
3 2 3
5 2 2
2 1 3
4 5
1 2 2
2 3 1
2 4 4
4 1 2
3 1 2
2 3
1 2 1
1 2 2
2 1 1
Output example #1
4
3 5 6 2 
-1
2
2 3 
Source XXV Командный чемпионат школьников Санкт-Петербурга по программированию Санкт-Петербург, Университет ИТМО, 5 ноября 2017 года