|
N островов соединены верёвочными мостами. Разбойникам предстояло пройти с острова A на остров B. Ради интереса, проходя по мосту, они поджигали его. Атаману стало интересно: возможно ли пройти с острова A на остров B, посетив все острова, и чтобы все мосты были сожжены?
Вам необходимо написать программу, которая поможет Атаману решить эту задачу.
Входные данные:
В первой строке через пробел вводится количество островов N и количество мостов K.
Следующие K строк содержат описания мостов. Каждый мост представляет собой пару чисел (номера островов), соединённых знаком "-". Например: 1-2, 5-4, 6-10. Возможно, что какие-то пары островов соединены более чем одним мостом.
Последняя строка содержит 2 числа A и B, разделённых пробелом - номера начального и конечного островов.
Выходные данные:
Необходимо вывести последовательность номеров островов через пробел, в порядке, котором необходимо их обойти, или NO, если задачу Атамана решить невозможно.
Ограничения:
1 <= N <= 1000; 0 <= K <= 10000
| Входные данные |
Выходные данные |
3 2
1-2
2-3
1 3 |
1 2 3 |
3 2
1-2
1-2
1 2 |
NO |
|
