문제 담당자는 일하지 않는다!

문장 담당, 중개인, 원안 담당자 사이의 대화입니다.

문장 담당: 무리예요, 이건

중개인: 뭐가요?

문장 담당: 뭐가가 아니라! 이걸 어떻게 자연스러운 문제 설정으로 만들라는 거예요?

중개인: 하하. 그걸 생각하는 게 자네 일이지. 문장 담당이잖나?

문장 담당: 떠넘겨도 정도가 있죠. 우선 게임 규칙부터 너무 부자연스러워요.

중개인: 그런가? 나는 흔한 돌 줄이기 게임이라고 생각하는데.

문장 담당: 플레이어 마음대로 돌을 무한히 늘릴 수 있는 돌 줄이기 게임이 흔할 리가 없잖아요!

중개인: 오, 자네 지금 재치 있는 말을 했네.

문장 담당: 네, 마음대로……. 아니 그건 됐고! 그쪽도 좀 생각해 주세요.

중개인: 글쎄, 목을 맨 의사의 유지를 이은 유자(遺子)의 의지로 돌을 가져간다는 건 어떤가?

문장 담당: 생각할 곳이 거기가 아니잖아요! 돌 줄이기 게임 얘기라고요!

중개인: 아닌가? 그런데 '取り(취하기)'는 같은 발음의 '鳥(새)' 말고는 쓸 말이 없어서 어렵다니까.

문장 담당: 말장난은 그만하세요! 자연스러운 문제 설정을 생각해 달라고 부탁하는 거예요!

중개인: 그건 자네 일이지. 나는 그냥 중개인이야. 원안 담당과 문장 담당 사이를 이어 줄 뿐이라고.

문장 담당: 젠장……. 원안 담당은 왜 이런 골치 아픈 문제를 낸 거야…….

중개인: 원안 담당자가 자네에게 전하는 말이야. "흐흐 실컷 고생해라, 문장 담당."

문장 담당: 저 녀석 두고 보자! 언젠가 한 대 칠 거야!

중개인: 내가 준 "돌이 늘어나는 돌 줄이기 게임은 설정하기 어렵지 않은가?"라는 조언도 조금은 도움이 됐을 거야.

문장 담당: 아니, 당신도요! 언젠가가 아니라 지금 칠게요!

중개인: 하하하. 자네가 마감까지 문장 담당의 역할을 못 해내면, 내가 멋대로 문제 문장을 써 버리겠네.

문장 담당: 잠깐, 당신이 쓴다고요?

중개인: 제목은 "문제 담당자는 일하지 않는다!"로 하고, 본문에는 우리가 나눈 이 대화를 그대로 싣겠네.

문장 담당: 제발 그만둬요! 그렇게 황당한 문제가 제 이름으로 세상에 나오면 다들 뭐라고 하겠어요!

중개인: 하하하. 마감도 못 지키는 사람은 사회적으로 매장당해도 싸지.

문장 담당: 젠장! 이렇게 된 이상 무슨 수를 써서라도 자연스러운 문제 설정을 떠올리고 말겠어!

(※ 결국 그대로 게재되었습니다)

$N$개의 점으로 이루어진 방향 그래프가 있다. 이 그래프에는 사이클이 없다. 각 점에는 돌이 몇 개씩 놓여 있다. 이 그래프를 이용해 두 명의 플레이어가 게임을 한다. 두 플레이어는 번갈아 가며 차례를 진행한다. 자신의 차례에 플레이어는 점 $v$를 고르고, 거기 놓인 돌을 1개 이상 가져간다. 그다음 $v$에서 $w$로 간선이 이어진 모든 점 $w$에 대해, $w$에 놓인 돌의 개수를 원하는 만큼 바꿀 수 있다(늘려도, 줄여도, 그대로 두어도 된다). 이를 반복하며, 가져갈 돌이 먼저 없어진 쪽이 진다.

두 플레이어가 최선을 다할 때 선공과 후공 중 누가 이기는지, 아니면 게임이 끝나지 않는지 구하라.

첫 줄에는 정수 $N$ ($2 \le N \le 1000$)과 $M$ ($1 \le M \le 10000$)이 공백으로 구분되어 주어진다. 이는 방향 그래프가 $N$개의 점과 $M$개의 간선으로 이루어져 있음을 뜻한다. 점에는 1번부터 $N$번까지 번호가 매겨져 있다.

이어지는 $N$개의 줄에는 정수 $v_i$ ($1 \le v_i \le 10000$)가 하나씩 주어진다. $i+1$번째 줄의 $v_i$는 $i$번 점에 처음에 돌이 $v_i$개 놓여 있음을 뜻한다.

이어지는 $M$개의 줄에는 정수 $a_i$, $b_i$ ($1 \le a_i, b_i \le N$)가 공백으로 구분되어 주어진다. 이는 $a_i$번 점에서 $b_i$번 점으로 가는 간선이 있음을 뜻한다. 자기 자신으로 가는 간선은 없으며, 한 점 $A$에서 다른 점 $B$로 가는 간선은 많아야 1개이다.

주어진 방향 그래프에는 사이클이 없다고 가정해도 된다.

N M
v1
v2
.
.
.
vN
a1 b1
a2 b2
.
.
.
aM bM

선공이 이기면 1을, 후공이 이기면 2를, 게임이 끝나지 않으면 0을 출력한다.