No.3340 Simple Graph Game
タグ : / 解いたユーザー数 54
作問者 :
noya2
Problem Statement
There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$, and the $i$-th edge is a directed edge from vertex $U_i$ to vertex $V_i$. Alice and Bob play the following game on this graph using $1$ piece. Initially, the piece is placed on vertex $1$. With Alice moving first and Bob moving second, they alternately repeat the following operation.
- Let $u$ be the vertex on which the piece is currently placed. Choose a vertex $v$ such that there exists an edge from vertex $u$ to vertex $v$, and move the piece to vertex $v$.
The player who cannot move the piece loses, and the player who did not lose wins. Also, if the game is not decided even after the two players have moved the piece $10^{100}$ times in total, the game is a draw. Both players want to win but also do not want to lose, so they prefer a draw to a loss, and a win to a draw. Determine which player wins, or whether the game ends in a draw, when both players act optimally.
Constraints
- $1 \le N \le 2 \times 10^5$
- $1 \le M \le \min (2 \times 10^5, \space N^2)$
- $1 \le U_i,V_i \le N \space (1 \le i \le M)$
- All given values are integers.
- The given directed graph does not contain multiple edges.
Input
$N\ M$ $U_1\ V_1$ $U_2\ V_2$ $\vdots$ $U_M\ V_M$
Output
Print Alice if Alice wins, Bob if Bob wins, and Draw if the game is a draw.
Sample
Sample 1
Input
4 4 1 2 2 3 3 4 2 4
Output
Bob
Sample 2
Input
3 3 1 2 2 3 3 1
Output
Draw
Sample 3
Input
3 3 1 2 2 1 1 3
Output
Alice
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。