악명 높은 교대 게임

첩보원들은 서열을 정할 때 머리싸움을 즐긴다. 그중 하나가 악명 높은 교대 게임이다. 두 사람이 하며, 한 명은 짝수 참가자, 다른 한 명은 홀수 참가자를 맡는다. 이 이름이 곧 승리 조건이다. 게임이 끝났을 때 이동 횟수가 짝수면 짝수 참가자가 이기고, 홀수면 홀수 참가자가 이긴다.

게임은 미리 준비한 판 위에서 진행한다. 판은 장소와, 특정 장소 쌍을 잇는 일방통행 연결로 이루어진다. 장소마다 그곳을 관리하는 참가자가 정해져 있다. 시작 장소에 말을 올려놓으면 게임이 시작된다. 매 차례, 말이 놓인 장소를 관리하는 참가자가 그 장소에서 나가는 연결 중 하나를 골라 말을 옮겨야 한다. 더 이상 옮길 수 없으면 게임이 끝나고 승자가 정해진다. 모든 판은 게임이 무한히 이어지지 않도록 만들어져 있다.

규칙상 두 첩보원은 누가 어느 참가자를 맡을지 미리 합의해야 한다. 첩보원들은 이 선택이 게임에서 가장 중요하다는 사실을 알아냈다. 특수 요원 워커는 서열을 올리려고 자기가 하는 게임을 모두 이기려 한다. 시작할 때 어느 참가자를 골라야 하는지만 알면 워커는 완벽하게 둔다. 게다가 원하는 쪽을 반드시 맡을 수 있는 특별한 기술도 익혀 뒀다. 주어진 판에서 워커가 골라야 할 참가자를 알려주면 된다. 틀리면 워커가 실망하니 정확해야 한다.

예를 들어 장소가 6개인 판을 보자. 짝수 참가자가 2번, 3번, 6번을 관리하고 홀수 참가자가 1번, 4번, 5번을 관리한다. 연결은 1에서 2, 1에서 3, 1에서 5, 2에서 3, 3에서 4, 3에서 5, 5에서 6으로 나 있고 말은 1번에서 시작한다. 먼저 두는 쪽은 홀수 참가자지만 그래도 진다. 말을 1에서 3으로 옮기면 짝수 참가자가 곧바로 4로 옮겨 이긴다. 1에서 2로 옮기면 짝수 참가자가 3으로 옮기고(다른 수가 없다) 이어서 5로 옮긴다. 그러면 홀수 참가자는 6으로 옮길 수밖에 없고, 네 번 움직였으므로 진다. 처음에 5로 옮겨도 마찬가지로 짝수 참가자가 이긴다.

첫 줄에 테스트 케이스의 개수를 나타내는 양의 정수가 주어진다. 이 값은 100 이하이다. 이어서 각 테스트 케이스가 다음 형식으로 주어진다.

• 한 줄에 공백으로 구분된 세 정수 $n$, $c$, $s$가 주어진다 ($1 \le n \le 10000$, $0 \le c \le 100000$, $1 \le s \le n$). 각각 장소의 수, 판에 있는 연결의 수, 말이 시작하는 장소이다.
• 다음 $n$개 줄에 정수 $p_i$가 하나씩 주어진다. $i$번 장소를 관리하는 참가자를 뜻하며, 짝수 참가자는 0, 홀수 참가자는 1이다.
• 다음 $c$개 줄에 공백으로 구분된 두 정수 $a$와 $b$가 주어진다 ($1 \le a, b \le n$). $a$번 장소에서 $b$번 장소로 가는 연결이 있다는 뜻이다.

각 테스트 케이스마다 워커가 이기려면 골라야 하는 참가자를 한 줄에 출력한다. 짝수 참가자면 0, 홀수 참가자면 1이다. 두 참가자 중 정확히 한 명에게만 필승 전략이 있으므로 답은 하나로 정해진다.