Problem J: 問題文担当者は働かない！

N 個の点からなる有向グラフがある。このグラフに閉路はない。それぞれの点には、いくつかの石が置かれている。このグラフを使って、２人のプレイヤーがゲームをする。おのおのの手番は、交互に訪れる。各プレイヤーは、自分の手番において、頂点v を選び、そこに置かれた石を１つ以上取り除く。その後、v からw に辺が張られているすべての頂点w について、w に置かれている石の個数を自由に変化させることができる（いくつ増やしても、いくつ減らしても、変化させなくてもよい）。これを繰り返して、最初に取る石がなくなった方の負けである。両者が最善をつくしたとき、先手と後手、どちらが勝つか。もしくは、いつまでもゲームが終わらないか。

「……いや、無理でしょう、これ」
「何が？」
「何がじゃなくて！　これにどうやって自然な問題設定をつけろって言うんですか」
「ははは。それを考えるのが君の仕事じゃないか。文章担当だろう？」
「丸投げにもほどがありますよ……。まずゲームのルールが不自然すぎるでしょう」
「そうかなぁ？　僕はよくある石取りゲームだと思うけどね」
「プレイヤーの意思で石を無尽蔵に増やせる石取りゲームがよくあってたまりますか！」
「お。君、今うまいこと言ったね」
「ええ、意思で石を……ってどうでもいいわ！　そっちも少しは考えてくださいよ」
「そうだねぇ。縊死した医師の遺志を継ぐ遺子の意思で石を取る、なんてどうだい？」
「考えるのはそこじゃねぇよ！　石取りゲームの話だよ！」
「違うのかい？　でも『取り』は鳥くらいしか同音異義語がなくて難しいんだよね」
「いったん言葉遊びから離れろや！　自然な問題設定を考えてくれって言ってるんですよ！」
「だからそれは君の仕事だろうに。僕はただの仲介役。原案担当と文章担当の間をとりもつだけさ」
「くそ……。原案担当め、どうしてこんな厄介な問題を……」
「原案担当者から君へのメッセージ。『フヒヒｗ　存分に苦しめ文章担当ｗｗ』だそうだよ」
「畜生あの野郎！　いつか一発殴る！」
「まあ、僕の『石が増える石取りゲームなんて実に設定がつけにくいと思わないかい？』ってアドバ イスのおかげもあるだろうけどね」
「畜生お前もか！　いつかと言わず今殴る！」
「はっはっは。君が締め切りまでに文章担当としての役割を果たせないようなら、僕が勝手に問題文 を書いちゃうよ？」
「殴……って、え？　お前が書いてくれんの？」
「タイトルは『問題文担当者は働かない！』。本文には、僕たちのこの会話をそのまま掲載」
「頼むからやめて！　そんなふざけた問題が自分名義で世に出たら、これから皆になんて言われる か！」
「はっはっは。締め切りも守れないような奴は、社会的に抹殺されて当然だよね」
「畜生！　こうなったら、意地でも自然な問題設定を思いついてやらあああああ！」

（※　結局そのまま掲載されました）

Input

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

入力の１行目には、整数N（2 ≤ N ≤ 1,000）と整数M（1 ≤ M ≤ 10,000）が、空白区切りで書かれている。これは、有向グラフがN 個の点とM 本の辺からなることをあらわす。頂点には、1 番からN 番までの番号がふられている。

続くN 行には、整数vi（1 ≤ vi ≤ 10,000）が書かれている。１＋ i 行目に書かれた整数vi は、i 番の点に最初はvi 個の石が置かれていることをあらわす。

続くM 行には、整数ai（1 ≤ ai ≤ N）と整数bi（1 ≤ bi ≤ N）が、空白区切りで書かれている。１＋N ＋ i 行目に書かれた整数ai とbi は、ai 番の点からbi 番の点へ張られている辺が存在することをあらわす。ある点から自分自身へと張られる辺は存在せず、ある点A からある点B へ張られる辺は高々１本である。

与えられた有向グラフには閉路がないと仮定してよい。

Output

両プレイヤーが自身の勝利を目指して最善をつくしたとき、先手が勝つならば1 を、後手が勝つなら ば2 を、いつまでもゲームが終わらないならば0 を出力せよ。

Sample Input 1 

6 5
7
14
5
11
2
5
1 2
2 3
3 4
4 5
5 6

Sample Output 1 

2

Sample Input 2 

5 7
295
127
350
982
426
1 5
3 5
4 2
3 1
3 4
5 4
3 2

Sample Output 2 

1

Sample Input 3 

8 7
6
1
7
2
5
2
6
3
1 3
6 3
7 4
4 2
1 6
5 4
7 5

Sample Output 3 

2