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

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

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

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

Входные данные

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

Первая строка описания каждого теста содержит два целых числа n и m — количество городов и дорог (2 ≤ n;m ≤ 2 * 105). Следующие m строк содержат по три целых числа и описывают дороги в формате uivici — город, из которого выходит i-я дорога, город, в который она ведет, и тип её пейзажа (1 ≤ ui; vi ≤ n; 1 ≤ ci ≤ m; ui ̸= vi).

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

Выходные данные

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