Кольорові чарівники - 2#1933
Казкова країна складається з кількох міст, з'єднаних двосторонніми дорогами. З будь-якого міста країни можна дістатися до будь-якого іншого, або напряму, або через інші міста. Немає доріг, що з'єднують місто саме із собою, і між будь-якою парою різних міст є не більше однієї дороги.
У цій країні живуть жовті та сині чарівники. Коли жовтий чарівник проходить дорогою, він фарбує її у жовтий. Коли синій чарівник проходить дорогою, він фарбує її у синій. Якщо синю дорогу буде пофарбовано жовтим (або жовту — синім), фарби змішуються, і дорога стає зеленою — це найменш улюблений колір обох чарівників.
Цього року конференція чарівників проходить у столиці (місто ). І жовтий, і синій чарівники хочуть дістатися до столиці та бажають знати мінімальну кількість доріг, які обов'язково стануть зеленими, щоб обидва могли потрапити до столиці. Спочатку всі дороги не пофарбовані.
Початкові позиції жовтого та синього чарівників наперед невідомі, тому вам потрібно відповісти на це запитання для можливих початкових сценаріїв.
У першому рядку дано два цілих числа (1 \le n \le 10^5) і (1 \le m \le 500\,000) — кількість міст і доріг.
У другому рядку — одне ціле число (1 \le F \le n) — номер міста-столиці.
Кожен з наступних рядків містить по два цілих числа a_i і b_i (1 \le a_i, b_i \le n), які означають дорогу між містами a_i і b_i.
У наступному рядку міститься ціле число (1 \le k \le 10^5) — кількість можливих початкових розташувань чарівників.
Кожен із наступних рядків містить по два цілих числа — міста, в яких спочатку знаходяться жовтий та синій чарівники.
Для кожного з сценаріїв виведіть мінімальну кількість доріг, які неминуче стануть зеленими, щоб обидва чарівники змогли дістатися до столиці.
Приклад 1