#include #include //小数点出力用 //cout << fixed << setprecision(10) << ans; #include #include #include #include #include #include #include #include using ll = long long; using namespace std; #define modPHash (ll)((1LL<<61)-1) #define modP (ll)998244353 bool chkrng0idx(int pos, int sup) { return (0 <= pos && pos < sup); } int clk4(int num) { return (num - 2) * (num % 2); } void yn(bool tf) { cout << (tf ? "YES\n" : "NO\n"); } #define GRAPH_SIZE 200002 void ans(int num) { if (num == 1) { cout << "Alice\n"; } else if (num == 2) { cout << "Bob\n"; } else { cout << "Draw\n"; } } vector> SCC(vectornxt[], int V_NUM) { vectorvis(V_NUM); vectorlisted(V_NUM); stackpostOrder; stackS; for (int v = 0;v < V_NUM;v++) { if (vis[v])continue; S.push(v); while (!S.empty()) { int now = S.top(); if (vis[now]) { if (!listed[now]) { postOrder.push(now); listed[now] = 1; } S.pop(); continue; } vis[now] = 1; for (int i = 0;i < nxt[now].size();i++) { if (!vis[nxt[now][i]]) { S.push(nxt[now][i]); } } } } vectorrev[GRAPH_SIZE]; for (int v = 0;v < V_NUM;v++) { vis[v] = 0; for (int i = 0;i < nxt[v].size();i++) { rev[nxt[v][i]].push_back(v); } } vector>res; while (!postOrder.empty()) { vectortmp; if (vis[postOrder.top()]) { postOrder.pop(); continue; } S.push(postOrder.top()); postOrder.pop(); while (!S.empty()) { int now = S.top(); S.pop(); if (vis[now]) { continue; } vis[now] = 1; tmp.push_back(now); for (int i = 0;i < rev[now].size();i++) { if (!vis[rev[now][i]]) { S.push(rev[now][i]); } } } res.push_back(tmp); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; int M; cin >> M; vectornxt[200002]; vectorinv_nxt[200002]; for (int i = 0;i < M;i++) { int U, V; cin >> U >> V; U--; V--; nxt[U].push_back(V); inv_nxt[V].push_back(U); } auto S = SCC(nxt, N); int dp[200002] = { 0 }; for (int i = S.size() - 1;i >= 0;i--) { for (int j = 0;j < S[i].size();j++) { int k = S[i][j]; if (nxt[k].size() == 0) { dp[k] = 2; } bool z = 0; bool one = 0; bool two = 0; for (int l = 0;l < nxt[k].size();l++) { if (dp[nxt[k][l]] == 0) { z = 1; } if (dp[nxt[k][l]] == 1) { one = 1; } if (dp[nxt[k][l]] == 2) { two = 1; } } if (two) { dp[k] = 1; } else if(one){ dp[k] = 2; } } for (int j = 0;j < S[i].size();j++) { int k = S[i][j]; if (nxt[k].size() == 0) { dp[k] = 2; } bool z = 0; bool one = 0; bool two = 0; for (int l = 0;l < nxt[k].size();l++) { if (dp[nxt[k][l]] == 0) { z = 1; } if (dp[nxt[k][l]] == 1) { one = 1; } if (dp[nxt[k][l]] == 2) { two = 1; } } if (two) { dp[k] = 1; } else if (one) { dp[k] = 2; } } } ans(dp[0]); return 0; }