Интересная экскурсия
Во Флатландии n городов, соединенных m односторонними дорогами.
Туристическая компания планирует разработать живописный циклический маршрут по дорогам Флатландии. Маршрут должен начинаться и заканчиваться в одном и том же городе и проходить по дорогам в их направлении, посещая промежуточные города. Маршрут может посещать один город несколько раз, но должен проходить по каждой дороге не более одного раза.
Каждая дорога характеризуется типом своего пейзажа, который задается числом от 1 до m. Чтобы туристический маршрут был живописным, любые две соседние дороги в этом маршруте должны иметь разный тип пейзажа. Это же требование относится к первой и последней дороге маршрута, чтобы можно было начинать путешествовать, начиная с любого города маршрута.
Помогите компании разработать удовлетворяющий этим критериям маршрут, либо выясните, что сделать это е.
Входные данные
Входные данные состоят из нескольких тестов. В первой строке находится число 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.
Выходные данные
Выведите ответ для каждого теста.Если искомого маршрута не существует, следует вывести число «-1». Иначе, выведите число k — длину маршрута (2 ≤ k ≤ m). В следующей строке выведите k чисел e1; e2; : : : ; ek — номера дорог в том порядке, в каком они идут в этом маршруте. Все номера ei должны быть различны. Если подходящих маршрутов несколько, можно вывести любой из них.