問題一覧 > 通常問題

No.3340 Simple Graph Game

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 54
作問者 : irinoirino / テスター : ponjuice りすりす/TwoSquirrels jupiter_68 noya2
お気に入りにしたユーザー ProblemId : 12809 / 自分の提出
問題文最終更新日: 2025-11-13 19:27:16
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 作問ハッカソンコンテスト 003 Day1 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。