Алиса и Боб играют с графом. У них есть неориентированный граф без петель и кратных ребер. Все вершины графа имеют степень равную \(2\). Граф может содержать несколько компонент связности. Обратите внимание, что если такой граф имеет \(n\) вершин, он будет иметь ровно \(n\) ребер.
Алиса и Боб ходят по очереди. Алиса ходит первой. За один ход игрок может выбрать \(k\) (\(l \le k \le r\); \(l < r\)) вершин, которые образуют связный подграф, и удалить эти вершины из графа, включая все инцидентные ребра.
Игрок, который не может сделать ход, проигрывает.
Предположим, для примера, что они играют на заданном графе с заданными \(l = 2\) и \(r = 3\):
Следующие множества вершин допустимы для первого хода Алисы:
- \(\{1, 2\}\)
- \(\{1, 3\}\)
- \(\{2, 3\}\)
- \(\{4, 5\}\)
- \(\{4, 6\}\)
- \(\{5, 6\}\)
- \(\{1, 2, 3\}\)
- \(\{4, 5, 6\}\)
Пусть Алиса выбрала подграф
\(\{4, 6\}\).
Тогда следующие множества вершин допустимы для первого хода Боба:
- \(\{1, 2\}\)
- \(\{1, 3\}\)
- \(\{2, 3\}\)
- \(\{1, 2, 3\}\)
Пусть Боб выбрал подграф
\(\{1, 2, 3\}\).
Алиса не может сделать ход, поэтому она проигрывает.
Вам дан граф размера \(n\) и целые числа \(l\) и \(r\). Кто победит, если Алиса и Боб играют оптимально.
Примечание
В первом тесте даны те же входные данные, что и в условии.
Во втором тесте дан тот же граф, что и в условии, но \(l = 1\) и \(r = 2\)