Кольорові чарівники#1944
У чарівній країні міста з'єднані двосторонніми дорогами. З будь-якого міста можна дістатись до будь-якого іншого, або безпосередньо, або через інші міста. Зазначимо, що жодна дорога не з'єднує місто саме із собою, і між будь-якою парою різних міст існує не більше однієї дороги.
У цій країні є два чарівники: жовтий і синій. Коли жовтий чарівник проходить дорогою, він фарбує її в жовтий колір, а синій — у синій. Якщо жовта фарба наноситься поверх синьої, або навпаки, дорога набуває зеленого кольору, який обидва чарівники не люблять.
Цього року в столиці (місто ) відбувається з'їзд чарівників. Чарівники хочуть визначити мінімальну кількість доріг, які доведеться перефарбувати у зелений колір для досягнення столиці. Спочатку всі дороги нефарбовані.
Початкове місце перебування жовтого та синього чарівника не визначено заздалегідь. Тому задачу слід розв'язати для можливих варіантів початкового розташування.
Перший рядок містить два цілі числа: кількість міст (1 \leq n \leq 100) і кількість доріг (1 \leq m \leq 500).
Другий рядок містить номер столиці (1 \leq f \leq n).
Далі йдуть рядків, у кожному з яких по два числа a_i та b_i, що позначають дорогу між містами a_i і b_i.
Наступний рядок містить одне число (1 \leq k \leq 100) — кількість можливих початкових розташувань чарівників.
У наступних рядках записано по два числа — початкові міста жовтого та синього чарівників відповідно.
Для кожного з варіантів виведіть мінімальну кількість доріг, які треба забарвити у зелений колір, щоб обом чарівникам дістатися до столиці.
Приклад 1