#nullable enable #region var (_input, _iter) = (Array.Empty(), 0); T I() where T : IParsable { while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Split(' '), 0); return T.Parse(_input[_iter++], null); } #endregion static T[] Range(int n, Func F) => Enumerable.Range(0, n).Select(_ => F()).ToArray(); var n = I(); var m = I(); var edges = Range(m, () => (I() - 1, I() - 1)); var g = new StaticGraph(edges, n, true); var res = new int[2, n]; res[0, 0] = 1; int S(int v, int t) { var adjz = g.Adjacencies(v); var nt = 1 - t; var ses = 3; foreach (var (next, _) in adjz) { var nr = res[nt, next]; if (nr == 0) { res[nt, next] = 1; nr = S(next, nt); } if (nr == 3) return res[t, v] = 2; if (nr == 1) ses = 1; } return res[t, v] = ses; } var x = S(0, 0); Console.WriteLine(x == 1 ? "Draw" : (x == 2 ? "Alice" : "Bob")); class StaticGraph { public int N { get; } public bool Directed { get; } public ReadOnlySpan<(int next, int edgeIndex)> Adjacencies(int of) => _adjacencies.AsSpan()[_starts[of].._starts[of + 1]]; public ReadOnlySpan<(int Ab, int Ad)> Edges => _edges; readonly (int Ab, int Ad)[] _edges; readonly (int, int)[] _adjacencies; readonly int[] _starts; public StaticGraph(IReadOnlyList<(int, int)> edges, int n, bool directed) { var ez = edges.ToArray(); var el = ez.Length; var m = directed ? el : (el << 1); var starts = new int[n + 1]; for (var i = 0; i < el; i++) { var (ab, ad) = ez[i]; starts[ab + 1]++; if (!directed) starts[ad + 1]++; } for (var i = 0; i < n; i++) starts[i + 1] += starts[i]; var adjacencies = new (int, int)[m]; var counts = starts.AsSpan().ToArray(); for (var i = 0; i < el; i++) { var (ab, ad) = ez[i]; adjacencies[counts[ab]++] = (ad, i); if (!directed) adjacencies[counts[ad]++] = (ab, i); } N = n; Directed = directed; _adjacencies = adjacencies; _edges = ez; _starts = starts; } }