Гра страшних чергувань
Для підвищення свого соціального статусу шпигуни грають у хитромудрі ігри. Однією з таких ігор є гра з чергуванням ходів. У цій грі беруть участь два гравці: один називається "парний", а інший - "непарний". Імена гравців визначають переможця: парний гравець виграє, якщо загальна кількість ходів у грі буде парною, а непарний - якщо непарною.
Гра відбувається на спеціальному ігровому полі, що складається з позицій і односпрямованих зв'язків між ними. Кожна позиція контролюється одним із двох гравців. Гра починається з розміщення фішки на стартовій позиції. Під час кожного ходу гравець, який контролює поточну позицію фішки, повинен перемістити її вздовж одного з доступних з'єднань. Гра триває, поки фішку можна переміщувати. Коли переміщення стає неможливим, визначається переможець. Ігрові поля побудовані так, що нескінченні ігри виключені.
Перед початком гри суперники вирішують, хто з них буде яким гравцем. Шпигуни з'ясували, що вибір гравця є ключовим для перемоги. Спеціальний агент Уокер прагне вигравати кожну гру, щоб підвищити свій соціальний статус. Вона знає, як правильно грати, якщо знає, якого гравця обрати на початку. Вона розробила навички, які завжди допоможуть їй зробити правильний вибір. Ваше завдання - допомогти їй обрати правильного гравця для заданого ігрового поля. Переконайтеся, що ваш вибір правильний, щоб не розчарувати агента Уокер.
Розгляньмо візуальне представлення третього тесту. Чорним позначені позиції, контрольовані парним гравцем. Незважаючи на свій перший хід, непарний гравець програє. Якщо він перемістить фішку з 1 в 3, парний гравець виграє, перемістивши фішку в 4. Якщо непарний гравець перемістить фішку в 2, то парний спочатку перемістить її в 3 (як і повинен це зробити), а потім в 5, після чого непарному гравцеві доведеться перемістити фішку в 6 і програти (здійснено чотири ходи). Якщо перший хід зробити в 5, то автоматично виграє парний гравець.
Вхідні дані
Перша стрічка містить кількість тестів, не більше 100. Структура кожного тесту така:
Один рядок містить n, c і s (1 ≤ n ≤ 10000, 0 ≤ c ≤ 100000, 1 ≤ s ≤ n): кількість позицій, з'єднань і номер стартової позиції гри.
n рядків зі значенням p_i: гравець, що контролює позицію i, 0 для парного гравця і 1 для непарного.
c рядків з двома цілими a і b (1 ≤ a, b ≤ n), що вказують на з'єднання від a до b.
Вихідні дані
Для кожного тесту виведіть в окремому рядку 0 або 1, що вказують на гравця, якого повинна обрати агент Уокер для перемоги.