Для усовершенствования своего социального статуса шпионам приходится играть в остроумные и хитрые игры. Одной из них является игра страшных чередований. В нее играют два игрока, один из которых называется четным, а другой нечетным. Такие странные имена игроков используются для определения победителя: четный игрок выигрывает, если количество ходов в завершенной игре будет четным, нечетный игрок выигрывает, если количество ходов будет нечетным. Каждая игра происходит на специально подготовленном игровом поле, состоящего из позиций и однонаправленных связей между ними. Каждая позиция находится под контролем одного из двух игроков. Игра начинается установкой фишки в стартовую позицию игрового поля. За каждый ход игрок, контролирующий текущую позицию фишки, должен переместить ее вдоль одного из исходящих соединений. Процесс продолжается, пока передвижение фишки не станет невозможным - в этот момент определяется победитель игры. Все игровые поля построены таким образом, что бесконечные игры невозможны. Правила игры гласят, что соперники изначально должны принять решение, кто будет каким игроком. Шпионы обнаружили, что выбор игрока является наиболее важной частью игры. Специальный агент Уокер хочет выиграть каждую игру для улучшения своего социального статуса. Она умеет правильно вести игру, если знает какого из игроков следует выбрать в начале. Она разработала специальный набор навыков, который ей всегда обеспечит выбор необходимого игрока. Ваша задача - помочь ей выбрать правильного игрока для заданного игрового поля. Убедитесь что Ваш выбор правильный, чтобы не разочаровать агента Уокер. \includegraphics{https://static.e-olymp.com/content/22/22ee76d3164294b179ee455cae7193e3b961b673.jpg} Рассмотрим визуальное представление третьего теста. Черным обозначены позиции, контролируемые четным игроком. Несмотря на свой первый ход, нечетный игрок проигрывает. Если он передвинет фишку из \textbf{1} в \textbf{3}, четный игрок выигрывает, передвинув фишку в \textbf{4}. Если нечетный игрок передвигает фишку в \textbf{2}, то четный сначала передвигает ее в \textbf{3} (как и должен это сделать), а затем в \textbf{5}, после чего нечетному игроку придется передвинуть фишку в \textbf{6} и проиграть (совершено четыре хода). Если первый ход сделать в \textbf{5}, то автоматически выиграет четный игрок. \InputFile Первая строка содержит количество тестов, не большее \textbf{100}. Структура каждого теста следующая: \begin{itemize} \item в одной строке расположены \textbf{n}, \textbf{c} и \textbf{s }(\textbf{1 }≤ \textbf{n }≤ \textbf{10000}, \textbf{0 }≤ \textbf{c }≤ \textbf{100000}, \textbf{1 }≤ \textbf{s }≤ \textbf{n}): количество позиций, соединений и номер стартовой позиции игры. \item \textbf{n} строк со значением \textbf{p_i}: игрок, контролирующий позицию \textbf{i}, \textbf{0} для четного игрока и \textbf{1 }для нечетного. \item \textbf{c} строк с двумя целыми \textbf{a }и \textbf{b }(\textbf{1 }≤ \textbf{a}, \textbf{b }≤ \textbf{n}), указывающими на соединение от \textbf{a }к \textbf{b}. \end{itemize} \OutputFile Для каждого теста вывести в отдельной строке \textbf{0 }или \textbf{1}, указывающих на игрока, которого должна выбрать агент Уокер для победы.