Задача №1746. Достройте дороги
В Тридесятом государстве есть N городов, все города пронумерованы числами от 1 до \(N\). Между городами построены дороги — каждая дорога соединяет между собой два города.
Царь Тридесятого государства уволил министра транспорта за то, что дороги были в очень плохом состоянии. Новый министр транспорта, чтобы не повторить судьбу своего предшественника, решил, что он будет лично контролировать состояние дорог. А именно он решил, что раз в год он лично будет объезжать все дороги.
При этом министр транспорта очень ценит свое время, и считает, что если в процессе объезда ему придется дважды проехать по какой-то дороге, то когда он будет ехать по этой дороге второй раз, ему уже не придется проверять ее состояние, и это будет недопустимой тратой времени.
Министр транспорта живет в городе номер 1, и поэтому хочет, чтобы его путешествие начиналось в этом городе. Заканчиваться путешествие должно в городе номер K, где каждый год будет проходить всегосударственное совещание по вопросам планирования ремонта дорог на следующий год.
Определите, какое минимальное количество дорог нужно построить в Тридесятом царстве в дополнение к уже существующим, чтобы можно было выполнить все требования Министра транспорта, а именно, чтобы он мог, выехав из города номер 1, проехать по каждой дороге ровно 1 раз и в итоге приехать в город номер \(K\).
Вводится число \(N\) — количество городов в Тридесятом царстве (1≤\(N\)≤100). Далее вводится число \(M\) — количество дорог в Тридесятом царстве (1≤\(M\)≤10000). Далее идет \(M\) пар чисел — каждая пара задает номера городов, соединяемых соответствующей дорогой. Все дороги двухсторонние, т.е. по дороге можно ездить в любую сторону. Между некоторыми городами может быть несколько дорог. Возможны дороги из города в него же. В последней строке входных данных находится число \(K\) — номер города, где заканчивается маршрут министра (1≤\(K\)≤\(N\)).
Выведите минимальное количество дорог, которое необходимо построить в Тридесятом царстве. Затем выведите, какие именно дороги надо построить: для каждой дороги выведите, какие города она должна соединять.
4 2 2 3 3 4 1
2 1 2 4 1
6 5 1 2 2 3 3 4 4 2 6 6 1
2 1 6 2 6
2 4 1 2 1 2 1 1 1 2 2
0