Person responsible for problem description don't w

時間制限 : 8 sec, メモリ制限 : 65536 KB

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

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

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

(※ 結局そのまま掲載されました)

Input

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

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

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

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

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

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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2010 , Day 2, Tokyo, Japan, 2010-09-18
http://acm-icpc.aitea.net/