22557번 - 問題文担当者は働かない！ 다국어

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 行には、整数v_i（1 ≤ v_i ≤ 10,000）が書かれている。１＋ i 行目に書かれた整数v_i は、i 番の点に最初はvi 個の石が置かれていることをあらわす。

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

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

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