В Берляндском государственном университете теперь можно учиться онлайн! Для получения диплома среди всего многообразия онлайн-курсов Поликарпу необходимо пройти k главных онлайн-курса его специальности. Всего для прохождения доступны n курсов.
Ситуация осложняется тем, что онлайн-курсы зависят друг от друга и для каждого курса есть список тех, которые необходимо обязательно пройти до начала прохождения этого онлайн-курса (список может быть пустым, что означает отсутствие таких ограничений).
Помогите Поликарпу пройти наименьшее количество курсов суммарно, чтобы получить cпециальность (то есть пройти все главные курсы и необходимые для их прохождения курсы). Напишите программу, которая выводит порядок прохождения курсов.
Поликарп проходит курсы последовательно, то есть он может приступать к прохождению следующего только после окончания предыдущего. Каждый из курсов можно проходить не более одного раза.
Выходные данные
Выведите -1, если не существует способа получения специальности.
В противном случае в первую строку выведите целое число m — минимальное количество онлайн-курсов, которое необходимо пройти для получения специальности. Во вторую строку выведите m различных целых чисел — номера курсов, которые надо пройти, в хронологическом порядке их прохождения. Если ответов несколько разрешается вывести любой из них.
Примечание
В первом примере можно сначала пройти курсы номер 1 и 2, после чего можно будет пройти курс номер 4, а затем курс номер 5, который является главным. После этого останется пройти только курс номер 3, который является последним непройденным главным курсом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2
5 3
0
0
0
2 2 1
1 4
1 5
|
5
1 2 3 4 5
|
|
2
|
9 3
3 9 5
0
0
3 9 4 5
0
0
1 8
1 6
1 2
2 1 2
|
6
1 2 9 4 5 3
|
|
3
|
3 3
1 2 3
1 2
1 3
1 1
|
-1
|