Цікава екскурсія
У Флатландії є 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 повинні бути різними. Якщо існує кілька підходящих маршрутів, можна вивести будь-який з них.