/* -*- coding: utf-8 -*- * * 3340.cc: No.3340 Simple Graph Game - yukicoder */ #include #include #include #include using namespace std; /* constant */ const int MAX_N = 200000; enum {Draw, Win, Lose}; const char ss[3][8] = {"Draw", "Alice", "Bob"}; /* typedef */ using vi = vector; using qi = queue; /* global variables */ vi nbrs[MAX_N], rnbrs[MAX_N]; int pns[MAX_N], fs[MAX_N]; /* subroutines */ /* main */ int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; nbrs[u].push_back(v); rnbrs[v].push_back(u); pns[u]++; } qi q; for (int u = 0; u < n; u++) if (pns[u] == 0) q.push(u); fill(fs, fs + n, Draw); while (! q.empty()) { int u = q.front(); q.pop(); int wc = 0; for (auto v: nbrs[u]) { if (fs[v] == Lose) { fs[u] = Win; break; } else if (fs[v] == Win) wc++; } if (wc == nbrs[u].size()) fs[u] = Lose; for (auto v: rnbrs[u]) if (--pns[v] == 0 || fs[u] == Lose) q.push(v); } puts(ss[fs[0]]); return 0; }