Ігри на графі#2404
Суперник почав -.
Я проаналізував його архітектуру й здався.
_______________________________________________
З мемуарів 20-го чемпіона світу Фріца Рибкіна
Прибувши на місце, Ааз одразу зажадав провести нараду букмекерів, на якій він виклав свій план.
- Головна задача, — почав Ааз свій виступ перед букмекерами, — навчитися використовувати досягнення прогресу. Ми плануємо запуск багатьох нових типів змагань, що — цілком можливо — призведе до появи ігор із правилами, не придуманими нами. Отже, потрібно швидко визначати, наскільки ці правила можуть бути для нас корисними.
- А чи можна хоча б загалом пояснити, як це буде робитися? — пролунало запитання із зали.
- Ось приклад задачі, розв'язавши яку, ми зможемо розібратися з цілим класом ігор. Дано орієнтований граф деякої гри для двох гравців і початкову позицію в ній. Нагадаємо, що у грі на графі гравець має право перейти з поточної позиції в будь-яку позицію, до якої існує ребро з поточної. Гравці ходять по черзі; програє той, хто не може зробити хід. Потрібно перевірити, чи вірно, що при будь-якій грі сторін завжди виграє перший гравець.
У вхідному файлі міститься опис одного або кількох тестів. У першому рядку кожного тесту задано число вершин і число ребер (1 \leq V \leq 100000, 1 \leq E \leq 100000), а також номер початкової позиції (1 \leq a \leq V). Далі йде рядків — опис ребер у форматі u_i\ v_i (1 \leq u_i, v_i \leq V), що означає наявність ребра, спрямованого з вершини u_i у вершину v_i. Файл завершується трьома нулями. Сума всіх по всіх тестах не перевищує , а кількість тестів у файлі не перевищує .
Дотримуйтеся формату прикладу максимально точно — перевірка здійснюється автоматично.
Приклад 1