eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Отъезд

Отъезд

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Близится время отъезда и, чтобы он получился организованным, каждый ЛКШонок должен знать номер автобуса на котором он поедет в Москву. В этом году ожидаются настолько вместительные автобусы, что каждый из них способен вместить всех ЛКШат.

Автобусов будет ровно два. Зачем два? Дело в том, что про некоторых ЛКШат мы знаем, что их ни в коем случае нельзя сажать в один автобус. Про других ЛКШат мы наоборот знаем, что они обязательно должны быть в одном автобусе.

Помогите нам распределить ЛКШат по автобусам.

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

В первой строке входного файла находится число n (1n10000) - количество ЛКШат. Во второй строке находится число m (1m100000) - количество пар ЛКШат на которые администрация будет обращать особое внимание при распределении по автобусам. Следующие m строк содержат по три целых числа i, j и k каждая (1i, jn; 1k2). Если k равно одному, то ЛКШата i и j должны обязательно сидеть в одном автобусе. Если k равно двум, то ЛКШата i и j должны обязательно сидеть в разных автобусах.

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

В первой строке выходного файла выведите количество детей в первом автобусе. Во второй строке через пробел выведите номера ЛКШат, которые будут сидеть в первом автобусе. Если рассадка невозможна, то выведите -1. Если существует несколько рассадок, то выведите любую.

Пример

Входные данные #1
7 6
1 2 2
3 4 2
5 6 2
1 3 1
4 6 1
4 7 1
Выходные данные #1
3
1 3 5