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

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

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

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

Вхідні дані

Перший рядок містить кількість міст n (1 ≤ n ≤ 100) та доріг m (1 ≤ m ≤ 500) у чарівній країні відповідно. Третій рядок містить номер міста f (1 ≤ f ≤ n), яке є столицею казкової країни. У наступних m рядках знаходиться опис доріг країни. У цих m рядках записано по два цілих числаai та bi, які означають, що існує дорога, яка з'єднує міста ai та bi. Наступний рядок містить кількість k (1 ≤ k ≤ 100) можливих початкових розміщень чарівників. Далі йде k рядків, кожен з яких містить два цілих числа — номери міст, у яких спочатку знаходяться жовтий та синій чарівники відповідно.

Вихідні дані

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