Казкова країна являє собою множину міст, з'єднаних дорогами з двостороннім рухом. Причому з довільного міста країни можна дістатись в довільне інше місто або безпосердньо, або через інші міста. Відомо, що в казковій країні не існує доріг, що з'єднують місто саме з собою, та між довільними двома різними містами існує не більше однєї дороги.

В казковій країні живуть жовтий та синій чарівники. Жовтий чарівник, проходячи по дорозі, перефарбовує її в жовтий колір, синій — в синій. Як відомо, при накладанні жовтої фарби на синюю, або синьої фарби на жовту, фарби змішуються і перетворюються в фарбу зеленого кольору, яка є самим нелюбимим кольором обох чарівників.

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

Початкове положення жовтого та синього чарівників наперед не відомо. Тому потрібно розв'язати дану задачу для k можливих випадків їх початкових розміщень.

Вхідні дані

Перший рядок містить цілі числа: n (1 ≤ n ≤ 105) та m (1 ≤ m ≤ 500000) - кількість міст та доріг в чарівній країні відповідно. Третій рядок містить одне ціле число F (1 ≤ F ≤ n) - номер міста, що є столицею казкової країни. В наступних M рядках міститься опис доріг країни. В цих m рядках записано по два цілих числа ai та bi, які означають, що існує дорога, що з'єднує міста ai та bi. Наступний рядок містить ціле число k (1 ≤ k ≤ 105) - кількість можливих початкових розміщень чарівників. Далі йде K рядків, кожен з яких містить два цілих числа - номери міст, в яких на початку знаходяться жовтий та синій чарівники відповідно.

Вихідні дані

Для кожного з k тестів вивести мінімальну кількість доріг, які прийдеться пофарбувати в зелений колір чарівникам для того щоб дістатися до столиці.