Winning Strategy in a Directed Graph Game

This problem involves a two‐player game played on a directed graph (which may contain cycles). At the beginning of the game, a starting vertex s and a target vertex t are chosen, and a token is placed at s. The two players then take turns moving the token along the directed edges. A move consists of moving the token from the current vertex to one of its neighbors following the direction of the edge.

If a player moves the token to the target vertex t, that player wins immediately. Likewise, if a player has no valid moves on his/her turn, that player loses. It is assumed that both players play optimally.

The task is to decide whether there is a forced winning strategy for either player. The answer should be an integer:

• 1 if the first player can force a win,
• -1 if the second player can force a win, and
• 0 if neither player has a forced winning strategy.
</p>

In mathematical terms, if we denote by f(v, p) the outcome (from the perspective of the player whose turn it is) when the token is at vertex v and it is player p's turn, then our goal is to determine f(s, 0) where player 0 is the first player and player 1 is the second player.

An edge from vertex u to vertex v is represented as \(u \to v\). The recursive evaluation is as follows:

[ f(v, p) = \begin{cases} -1, & \text{if } v \neq t \text{ and there are no outgoing moves,}\ 1, & \text{if there exists a move } v \to t \text{ (immediate win)},\ \max { -f(u, 1-p) : u \text{ is a neighbor of } v } \quad & \text{with proper handling for cycles (considered as draws)}. \end{cases} ]

Note that if a cycle is encountered (i.e. a state is revisited during recursion), its outcome is taken to be 0 (draw), which might influence the overall decision.

inputFormat

The input consists of multiple lines. The first line contains two integers n and m denoting the number of vertices and edges respectively.

Each of the next m lines contains two integers u and v indicating a directed edge from vertex u to vertex v.

The last line contains two integers s and t representing the starting vertex and the target vertex.

outputFormat

Output a single integer: 1 if the first player has a forced win, -1 if the second player can force a win, or 0 if neither has a forced winning strategy.

sample

3 2
1 2
2 3
1 3

-1