Иван — учитель по программированию. В течение учебного года он планирует прочитать \(n\) лекций на \(n\) различных тем. Каждая тема должна быть использована ровно в одной лекции. Иван хочет выбрать, какую тему он будет объяснять во время \(1\)-й, \(2\)-й, ..., \(n\)-й лекции — формально он хочет выбрать некоторую перестановку целых чисел от \(1\) до \(n\) (назовем эту перестановку \(q\)). \(q_i\) — это номер темы, которую Иван объяснит во время \(i\)-й лекции.
Для каждой темы (за исключением ровно одной) существует обязательная предшествующая тема (для \(i\)-й темы предшествующая тема — \(p_i\)). Иван не может читать лекцию по теме, не прочитав лекцию по ее предшествующей теме. Существует по крайней мере один допустимый порядок тем в соответствии с этими предварительными ограничениями.
Правильный порядок тем может помочь студентам лучше понять лекции. У Ивана есть \(k\) специальных пар тем \((x_i, y_i)\) таких, что он знает, что студенты лучше поймут \(y_i\)-ю тему, если лекция по ней будет проводиться сразу после лекции по \(x_i\)-й теме. Иван хочет удовлетворить ограничениям на каждую такую пару, то есть для каждого \(i \in [1, k]\) должно существовать некоторое \(j \in [1, n - 1]\) такое, что \(q_j = x_i\) и \(q_{j + 1} = y_i\).
Теперь Иван хочет знать, существует ли порядок тем, удовлетворяющий всем этим ограничениям, и если хотя бы один из них существует, найти любой из них.
Выходные данные
Если не существует порядка тем, удовлетворяющих всем ограничениям, выведите \(0\).
В противном случае выведите \(n\) попарно различных целых чисел \(q_1\), \(q_2\), ..., \(q_n\) (\(1 \le q_i \le n\)) — порядок тем, удовлетворяющих всем ограничениям. Если ответов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
2 3 0 5 3
1 5
5 4
|
3 2 1 5 4
|
|
2
|
5 2
2 3 0 5 3
1 5
5 1
|
0
|
|
3
|
5 1
2 3 0 5 3
4 5
|
0
|
|
4
|
5 4
2 3 0 5 3
2 1
3 5
5 2
1 4
|
3 5 2 1 4
|