ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Неотсортированные > задача:


Где ключи?

Задачи раздела

• Всё как у людей
• Все любят уравнения
• Все любят уравнения
• Все любят уравнения
• Второй максимум последовательности
• Выбирайте типы данных с умом
• Вычёркивание
• Гангстеры
• Где ключи?
• Геймер
• Генератор случайных чисел
• Граф
• Граф
• Даты: вчера и завтра
• Даты: интервал между датами
• Даты: конструктор
• Даты: конструктор по номеру

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Где ключи?
Где ключи?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Найти ключи от кафедры ВТ не так просто, как можно подумать. Да, обычно они лежат в аудитории 304. Однако иногда там можно найти только записку «Ключи в ауд. 306». В свою очередь, там можно найти записку «Ключи в ауд. 300б». А там — две записки «Ключи в ауд. 300а» и «Ключи в ауд. 301б», причём ключи могут лежать в любой из этих аудиторий...

Будем считать, что на этаже N аудиторий; для простоты пронумеруем их от 1 до N. Васе нужно найти ключи от кафедры, и он начинает поиски с аудитории 1. Алгоритм действий Васи следующий:

  • Если Вася находит в аудитории ключи, он говорит «Keys found!» и заканчивает поиск;
  • Иначе Вася помечает в записной книжке, что он побывал в текущей аудитории. При этом Вася говорит «Mark X as visited», где X — номер текущей аудитории;
  • Вася начинает просматривать записки, оставленные в аудитории, в порядке увеличения номеров аудиторий на них. Допустим, что сейчас Вася просматривает записку, в которой указана аудитория Y.
    • Если Вася уже был в Y, он говорит «Y is already visited» и переходит к следующей записке;
    • Иначе Вася говорит «Go to Y» и идёт в аудиторию Y;
  • Если в аудитории не осталось непросмотренных записок, Вася говорит «Return back» и возвращается в аудиторию, из которой он пришёл в текущую.

Определите, в каком порядке Вася будет обходить аудитории.

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

Первая строка содержит целые числа N, M и K (1 ≤ N ≤ 100, 0 ≤ M ≤ 100, 1 ≤ K ≤ N) — соответственно количество аудиторий, количество записок и номер аудитории, в которой лежат ключи.

Следующие M строк описывают записки. Каждая из них содержит целые числа Xi и Yi (1 ≤ Xi, Yi ≤ N) — соответственно номер аудитории, в которой лежит i-я записка, и номер аудитории, указанный на i-й записке. Записки во входных данных не повторяются.

Гарантируется, что Вася найдёт ключи.

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

Выведите на отдельных строках все сообщения, сказанные Васей в процессе поисков.

Примеры

Входные данные
5 4 5
1 2
2 3
3 4
3 5
Выходные данные
Mark 1 as visited
Go to 2
Mark 2 as visited
Go to 3
Mark 3 as visited
Go to 4
Mark 4 as visited
Return back
Go to 5
Keys found!
Входные данные
6 13 6
3 2
3 5
1 2
4 1
6 1
2 6
2 5
5 6
6 3
1 5
1 3
2 4
3 4
Выходные данные
Mark 1 as visited
Go to 2
Mark 2 as visited
Go to 4
Mark 4 as visited
1 is already visited
Return back
Go to 5
Mark 5 as visited
Go to 6
Keys found!
Для отправки решений необходимо выполнить вход.

www.contester.ru