Задача №114833. Интересная экскурсия
Во Флатландии 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 чисел e 1 , e 2 , ..., e k — номера дорог в том порядке, в каком они идут в этом маршруте. Все номера e i должны быть различны. Если подходящих маршрутов несколько, можно вывести любой из них.
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
4 3 5 6 2 -1 2 2 3