E. Тренировочные сборы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Медер и Кылычбек вместе организуют тренировочные сборы для лучших спортивных программистов Кыргызстана.

Они уже объявили n учебных тем, с которыми участники сборов должны ознакомиться в процессе.

Но есть проблема — необходимо составить расписание сборов таким образом, чтобы оба преподавателя были довольны.

Во-первых, не все темы можно рассказывать друг за другом. Всего известно k связей учебных тем (fi, si) таких, что тему si можно рассказывать сразу после fi, причем тема si всегда строго сложнее темы fi.

Формально: гарантируется, что если есть связь (f, s), то не существует никакой последовательности связей, позволяющих после прочтения s рассказать f.

Во-вторых, у каждого преподавателя есть своя любимая тема, которую он предпочитает рассказывать в первый день сборов.

Ни с какой другой темы ни Медер, ни Кылычбек не согласятся начинать свою часть сборов.

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

В-третьих, итоговое расписание должно включать каждую из n заявленных тем хотя бы один раз (но оба преподавателя могут рассказать одну и ту же тему при необходимости).

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

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

В первой строке содержатся целые числа n и m (2 ≤ n ≤ 2·105,  1 ≤ m ≤ 2·105) — количество тем, планируемых для сборов, и количество связок тем.

Во второй строке содержатся целые числа tM и tK (1 ≤ tM, tK ≤ n,  tM ≠ tK) — номера любимых тем Медера и Кылычбека, соответственно.

В каждой из следующих m строк содержится по два целых числа fi и si (1 ≤ fi, si ≤ n,  fi ≠ si;si ≠ tM;si ≠ tK) — темы, входящие в i-ю связь (тему si можно прочитать после прочтения fi).

Гарантируется, что если есть связь (f, s), то не существует никакой последовательности связей, позволяющих после прочтения s рассказать f.

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

В первой строке выведите YES, если Медер и Кылычбек смогут прочитать все n тем, и NO в противном случае.

Если сборы получится провести, то выведите ещё четыре строки.

Во второй строке выведите целое число dM — количество тем, которые прочитает Медер, начав с темы tM.

В третьей строке выведите через пробел dM целых чисел — последовательность тем, которые прочтёт Медер, начиная с темы tM.

В четвёртой строке выведите целое число dK — количество тем, которые прочитает Кылычбек, начав с темы tK.

В пятой строке выведите через пробел dK целых чисел — последовательность тем, которые прочтёт Кылычбек, начиная с темы tK.

Примеры
Входные данные
6 7
1 2
1 3
1 4
2 3
2 4
3 5
4 5
3 6
Выходные данные
YES
3
1 3 6 
3
2 4 5
Входные данные
6 6
1 3
1 2
2 4
3 4
3 5
5 6
4 6
Выходные данные
YES
4
1 2 4 6 
3
3 5 6
Входные данные
6 5
1 2
1 3
2 3
3 4
3 5
3 6
Выходные данные
NO
Входные данные
5 5
1 2
1 3
2 3
3 4
2 4
4 5
Выходные данные
YES
4
1 3 4 5 
4
2 3 4 5
Примечание

Первый тестовый пример

  • Медер начал со своей любимой темы 1, перешёл к теме 3 и закончил свои лекции на теме 6.
  • Кылычбек начал со своей любимой темы 2, перешёл к теме 4 и закончил свои лекции на теме 5.

Суммарно преподаватели рассказали все n = 6 тем.

Второй тестовый пример

Медер и Кылычбек оба прочитали тему 6. Расписание, где тема 6 прочитана только одним из двух преподавателей, тоже было бы корректным.

Третий тестовый пример

Медер и Кылычбек не смогут прочитать за время сборов темы 4, 5 и 6 — только любые две из них.

Четвёртый тестовый пример

Либо Медер, либо Кылычбек могли прочитать только свою любимую тему и остановиться на этом — второй преподаватель всё равно прочитал бы все остальные темы сборов.