Точки и строки
Эндрю и Бетти играли в игру "Точки и линии" на уроке информатики. Они начинают с листа бумаги, на котором нарисованы n точек. Игроки ходят по очереди, и Эндрю делает первый ход. На каждом ходу игрок должен соединить линией две точки, которые еще не соединены напрямую. Например, на изображении ниже игрок может соединить точки 1 и 2, 2 и 4, или любую из точек 1, 2, 3, 4 с любой из точек 5, 6.
Если после хода игрока все точки становятся соединенными, то есть можно добраться от каждой точки до любой другой по линиям, этот игрок выигрывает игру.
Недавно Эндрю нашел лист бумаги с незаконченной игрой среди своих вещей. Он хочет узнать, кто выиграет игру, если он сделает следующий ход и оба игрока будут действовать оптимально. Помогите ему это выяснить.
Входные данные
Первая строка входного файла содержит n — количество точек, и m — количество уже нарисованных линий (2 ≤ n ≤ 150, 0 ≤ m ≤ n(n-1)/2).
Следующие m строк содержат по два целых числа — номера точек, соединенных линией.
Выходные данные
Выведите "Эндрю", если Эндрю выиграет игру, или "Бетти", если выиграет Бетти.