The Problem Writer Does Not Work!

Dialogue between the statement writer (W), the mediator (M), and the problem author (P).

W: No way, this one is impossible.

M: What is?

W: Not "what"! How am I supposed to give this a natural problem setting?

M: Ha ha. Figuring that out is your job. You are the statement writer, right?

W: Passing the work off is one thing, but this is too much. First, the game rules are unnatural.

M: Are they? I think it is an ordinary stone-taking game.

W: Since when is there a common stone-taking game where players can add stones at will without limit?

M: Oh, you just said something clever.

W: Yes, at will... no, forget that! You should think about it too.

M: Well then. How about this: a stone is taken by the will of a child who inherited the will of a doctor who hanged himself?

W: That is not what needs thinking about! This is about the stone-taking game!

M: Is it not? But "tori" (taking) has only "tori" (bird) as a homophone, which makes it hard.

W: Stop the wordplay! I am asking you to think of a natural problem setting!

M: That is your job. I am only the middleman between the problem author and the statement writer.

W: Damn... why did the problem author give me such a troublesome problem?

M: A message from the problem author to you: "Hehehe. Suffer, statement writer, lol lol."

W: Damn that guy! Someday I will punch him!

M: My advice that a stone-taking game where stones keep growing is very hard to set up may have helped a little, though.

W: Damn, you too! Not someday, I will punch you now!

M: Ha ha ha. If you fail to finish your part before the deadline, I will write the statement myself.

W: Wait, you will write it?

M: The title will be "The Problem Writer Does Not Work!" and the body will print our conversation as it is.

W: Please stop! If a silly problem like that is published under my name, what will everyone say?

M: Ha ha. Someone who cannot meet a deadline deserves to be socially erased, right?

W: Damn! Then I will come up with a natural problem setting no matter what!

(Note: in the end, it was published exactly as written here.)

There are $N$ vertices in a directed graph with no cycles. Each vertex holds some stones. Two players play a game on this graph. The players take turns. On his turn, a player chooses a vertex $v$ and removes one or more stones from it. Then, for every vertex $w$ with an edge from $v$ to $w$, the player may change the number of stones on $w$ freely (increase it by any amount, decrease it by any amount, or leave it unchanged). The game repeats, and the player who runs out of stones to take first loses.

If both players play optimally, which player wins: the first player or the second player? Or does the game never end?

The first line contains integers $N$ ($2 \le N \le 1000$) and $M$ ($1 \le M \le 10000$), separated by a space. The graph has $N$ vertices and $M$ edges. Vertices are numbered from 1 to $N$.

The next $N$ lines each contain an integer $v_i$ ($1 \le v_i \le 10000$). The integer $v_i$ on line $i+1$ is the number of stones initially on vertex $i$.

The next $M$ lines each contain integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$), separated by a space. They mean there is an edge from vertex $a_i$ to vertex $b_i$. There are no self-loops, and there is at most one edge from any vertex $A$ to any vertex $B$.

You may assume the given graph has no cycles.

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

If the first player wins, print 1. If the second player wins, print 2. If the game never ends, print 0.