Казкова країна являє собою множину міст, з'єднаних дорогами з двостороннім рухом. Причому з довільного міста країни можна дістатись в довільне інше місто або безпосердньо, або через інші міста. Відомо, що в казковій країні не існує доріг, що з'єднують місто саме з собою, та між довільними двома різними містами існує не більше однєї дороги.
В казковій країні живуть жовтий та синій чарівники. Жовтий чарівник, проходячи по дорозі, перефарбовує її в жовтий колір, синій — в синій. Як відомо, при накладанні жовтої фарби на синюю, або синьої фарби на жовту, фарби змішуються і перетворюються в фарбу зеленого кольору, яка є самим нелюбимим кольором обох чарівників.
В цьому році в столиці країни (місті F) проводиться конференція чарівників. Тому жовтий і синій чарівники хочуть взнати, яку мінімальну кількість доріг їм прийдеться перефарбувати в зелений колір, щоб дістатись в столицю. Спочатку всі дороги не пофарбовані.
Початкове положення жовтого та синього чарівників наперед не відомо. Тому потрібно розв'язати дану задачу для К можливих випадків їх початкових розміщень.

Вхідні дані
Перший рядок вхідного файлу містить цілі числа: N (1 ≤ N ≤ 100000) та M (1 ≤ M ≤ 500000) — кількість міст та доріг в чарівній країні відповідно. Третій рядок містить одне ціле число F (1 ≤ F ≤ N) — номер міста, що є столицею казкової країни. В наступних M рядках міститься опис доріг країни. В цих M рядках записано по два цілих числа Ai та Bi, які означають, що існує дорога, що з'єднує міста Ai и Bi. Наступний рядок містить ціле число K (1 ≤ K ≤ 100000) — кількість можливих початкових розміщень чарівників. Далі йде K рядків, кожен з яких містить два цілих числа— номери міст, в яких на початку знаходяться жовтий та синій чарівники відповідно.
Вихідні дані
Для кожного з K випадків ваша програма повинна вивести мінімальну кількість доріг, які прийдеться пофарбувати в зелений колір чарівникам для того, щоб дістатись в столицю.