Олимпиада проводится при поддержке Московского физико-технического института, Благотворительного фонда "Династия", компьютерной компании НИКС, Компании Yandex, компании Genius
Информационная поддержка:
журнал "Мир ПК"
III Всероссийская заочная олимпиада школьников по информатике, 2008/09 учебный год
Задача F. Достройте дороги (off-line проверка)
| Имя входного файла: | f.in |
| Имя выходного файла: | f.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
В Тридесятом государстве есть N городов, все города пронумерованы числами от 1 до N. Между городами построены дороги - каждая дорога соединяет между собой два города.
Царь Тридесятого государства уволил министра транспорта за то, что дороги были в очень плохом состоянии. Новый министр транспорта, чтобы не повторить судьбу своего предшественника, решил, что он будет лично контролировать состояние дорог. А именно он решил, что раз в год он лично будет объезжать все дороги.
При этом министр транспорта очень ценит свое время, и считает, что если в процессе объезда ему придется дважды проехать по какой-то дороге, то когда он будет ехать по этой дороге второй раз, ему уже не придется проверять ее состояние, и это будет недопустимой тратой времени.
Министр транспорта живет в городе номер 1, и поэтому хочет, чтобы его путешествие начиналось в этом городе. Заканчиваться путешествие должно в городе номер K, где каждый год будет проходить всегосударственное совещание по вопросам планирования ремонта дорог на следующий год.
Определите, какое минимальное количество дорог нужно построить в Тридесятом царстве в дополнение к уже существующим, чтобы можно было выполнить все требования Министра транспорта, а именно, чтобы он мог, выехав из города номер 1, проехать по каждой дороге ровно 1 раз и в итоге приехать в город номер K.
Формат входных данных
Вводится число N - количество городов в Тридесятом царстве (1≤N≤100). Далее вводится число M - количество дорог в Тридесятом царстве (1≤M≤10000). Далее идет M пар чисел - каждая пара задает номера городов, соединяемых соответствующей дорогой. Все дороги двухсторонние, т.е. по дороге можно ездить в любую сторону. Между некоторыми городами может быть несколько дорог. Возможны дороги из города в него же. В последней строке входных данных находится число K - номер города, где заканчивается маршрут министра (1≤K≤N).
Формат выходных данных
Выведите минимальное количество дорог, которое необходимо построить в Тридесятом царстве. Затем выведите, какие именно дороги надо построить: для каждой дороги выведите, какие города она должна соединять.
Примеры
| f.in | f.out | Комментарии |
4 2 2 3 3 4 1 |
2 1 2 1 4 |
4 города и 2 дороги: из 2 в 3 и из 3 в 4. Т.к. министр транспорта живет в городе 1, и совещание также будет в городе 1, необходимо достроить 2 дороги - из 1 в 2 и из 1 в 4, тогда министр сможет из 1-го города поехать во 2-й, оттуда - в 3-й, оттуда - в 4-й и вернуться в 1-й. |
6 5 1 2 2 3 3 4 4 2 6 6 1 |
2 2 6 6 1 |
Маршрут министра может быть, например, таким: 1, 2, 3, 4, 2, 6, 6. В 5-м городе вообще нет дорог, поэтому туда министру заезжать не нужно. А вот дорогу, ведущую из 6-го города в него же, он проверить обязательно должен. |
2 4 1 2 1 2 1 1 1 2 2 |
0 |
Маршрут министра может быть таким: 1, 1, 2, 1, 2. Новых дорог достраивать не нужно. |