N 個の点からなる有向グラフがある。このグラフに閉路はない。それぞれの点には、いくつかの石が置かれている。このグラフを使って、２人のプレイヤーがゲームをする。おのおのの手番は、交互に訪れる。各プレイヤーは、自分の手番において、頂点v を選び、そこに置かれた石を１つ以上取り除く。その後、v からw に辺が張られているすべての頂点w について、w に置かれている石の個数を自由に変化させることができる（いくつ増やしても、いくつ減らしても、変化させなくてもよい）。これを繰り返して、最初に取る石がなくなった方の負けである。両者が最善をつくしたとき、先手と後手、どちらが勝つか。もしくは、いつまでもゲームが終わらないか。
「……いや、無理でしょう、これ」
「何が？」
「何がじゃなくて！ これにどうやって自然な問題設定をつけろって言うんですか」
「ははは。それを考えるのが君の仕事じゃないか。文章担当だろう？」
「丸投げにもほどがありますよ……。まずゲームのルールが不自然すぎるでしょう」
「そうかなぁ？ 僕はよくある石取りゲームだと思うけどね」
「プレイヤーの意思で石を無尽蔵に増やせる石取りゲームがよくあってたまりますか！」
「お。君、今うまいこと言ったね」
「ええ、意思で石を……ってどうでもいいわ！ そっちも少しは考えてくださいよ」
「そうだねぇ。縊死した医師の遺志を継ぐ遺子の意思で石を取る、なんてどうだい？」
「考えるのはそこじゃねぇよ！ 石取りゲームの話だよ！」
「違うのかい？ でも『取り』は鳥くらいしか同音異義語がなくて難しいんだよね」
「いったん言葉遊びから離れろや！ 自然な問題設定を考えてくれって言ってるんですよ！」
「だからそれは君の仕事だろうに。僕はただの仲介役。原案担当と文章担当の間をとりもつだけさ」
「くそ……。原案担当め、どうしてこんな厄介な問題を……」
「原案担当者から君へのメッセージ。『フヒヒｗ 存分に苦しめ文章担当ｗｗ』だそうだよ」
「畜生あの野郎！ いつか一発殴る！」
「まあ、僕の『石が増える石取りゲームなんて実に設定がつけにくいと思わないかい？』ってアドバ
イスのおかげもあるだろうけどね」
「畜生お前もか！ いつかと言わず今殴る！」
「はっはっは。君が締め切りまでに文章担当としての役割を果たせないようなら、僕が勝手に問題文
を書いちゃうよ？」
「殴……って、え？ お前が書いてくれんの？」
「タイトルは『問題文担当者は働かない！』。本文には、僕たちのこの会話をそのまま掲載」
「頼むからやめて！ そんなふざけた問題が自分名義で世に出たら、これから皆になんて言われる
か！」
「はっはっは。締め切りも守れないような奴は、社会的に抹殺されて当然だよね」
「畜生！ こうなったら、意地でも自然な問題設定を思いついてやらあああああ！」
（※ 結局そのまま掲載されました）
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 へ張られる辺は高々１本である。
与えられた有向グラフには閉路がないと仮定してよい。
両プレイヤーが自身の勝利を目指して最善をつくしたとき、先手が勝つならば1 を、後手が勝つなら ば2 を、いつまでもゲームが終わらないならば0 を出力せよ。
6 5 7 14 5 11 2 5 1 2 2 3 3 4 4 5 5 6
2
5 7 295 127 350 982 426 1 5 3 5 4 2 3 1 3 4 5 4 3 2
1
8 7 6 1 7 2 5 2 6 3 1 3 6 3 7 4 4 2 1 6 5 4 7 5
2