Кольорові чарівники - 2
Казкова країна являє собою множину міст, з'єднаних дорогами з двостороннім рухом. Причому з довільного міста країни можна дістатись в довільне інше місто або безпосердньо, або через інші міста. Відомо, що в казковій країні не існує доріг, що з'єднують місто саме з собою, та між довільними двома різними містами існує не більше однєї дороги.
В казковій країні живуть жовтий та синій чарівники. Жовтий чарівник, проходячи по дорозі, перефарбовує її в жовтий колір, синій — в синій. Як відомо, при накладанні жовтої фарби на синюю, або синьої фарби на жовту, фарби змішуються і перетворюються в фарбу зеленого кольору, яка є самим нелюбимим кольором обох чарівників.
В цьому році в столиці країни (місті F) проводиться конференція чарівників. Тому жовтий і синій чарівники хочуть взнати, яку мінімальну кількість доріг їм прийдеться перефарбувати в зелений колір, щоб дістатись в столицю. Спочатку всі дороги не пофарбовані.
Початкове положення жовтого та синього чарівників наперед не відомо. Тому потрібно розв'язати дану задачу для k можливих випадків їх початкових розміщень.
Вхідні дані
Перший рядок містить цілі числа: n (1 ≤ n ≤ 10^5) та m (1 ≤ m ≤ 500000) - кількість міст та доріг в чарівній країні відповідно. Третій рядок містить одне ціле число F (1 ≤ F ≤ n) - номер міста, що є столицею казкової країни. В наступних M рядках міститься опис доріг країни. В цих m рядках записано по два цілих числа a[i] та b[i], які означають, що існує дорога, що з'єднує міста a[i] та b[i]. Наступний рядок містить ціле число k (1 ≤ k ≤ 10^5) - кількість можливих початкових розміщень чарівників. Далі йде K рядків, кожен з яких містить два цілих числа - номери міст, в яких на початку знаходяться жовтий та синій чарівники відповідно.
Вихідні дані
Для кожного з k тестів вивести мінімальну кількість доріг, які прийдеться пофарбувати в зелений колір чарівникам для того щоб дістатися до столиці.