2094. Игра с графом

В одном из очень известных графств завелись два азартных игрока: Алиса и Боб. Граф очень встревожен этим, потому что от таких игроков страдают люди и его графство. Вот и на этот раз Алиса и Боб придумали новую игру.

Опишем правила игры. Игроки делают ходы по очереди. На каждом ходе игрок выбирает дорогу, которая еще не разрушена, и разрушает ее. Если после хода игрока, граф видит, что из какого-то города нельзя добраться во все остальные по неразрушенным дорогам, то он выгоняет этого игрока из графства за порчу имущества, и этот игрок проигрывает в игре своему оппоненту.

Известно, что графство состоит из городов и дорог, причем каждая дорога соединяет ровно два города. По дорогам можно перемещаться в обоих направлениях. Не существует дорог, которые соединяет город сам с собой, и каждую пару городов соединяет не более одной дороги. Из каждого города можно добраться во все другие города.

Известно, что каждый из игроков хочет выиграть, поэтому действует всегда оптимально.

Вам задано графство и известно, что Боб, как джентельмен, уступает первый ход Алисе. Вам нужно понять, кто проиграет в данной игре.

В первой строке входного файла заданы два целых числа `n` и `m` (`1\ ≤\ n\ ≤\ 100`, `0\ ≤\ m\ ≤\ 500`) – количество городов и дорог соответственно. В следующих `m` строках заданы дороги – два числа: `a` и `b` (`1\ ≤\ a\ <\ b\ ≤\ n`) – номера городов, которые соединяет соответствующая дорога.

Гарантируется, что никакая пара городов не встречается во входном файле дважды и что из любого города можно добраться до всех остальных по заданным дорогам. В выходной файл выведите имя игрока, который проиграл: Alice или Bob, либо Draw, если никто не проиграл.

3 3
1 2
1 3
2 3

Bob

2 1
1 2

Alice

В первом примере Алиса разрушает любую из трех дорог. После этого Боб, вне зависимости от своего хода, он проигрывает.

Во втором примере всего одна дорога, разрушив ее, Алиса проиграет.