Рассмотрим таблицу $$$(10^9+1) \times (10^9+1)$$$. Строки пронумерованы целыми числами от $$$0$$$ до $$$10^9$$$, и столбцы пронумерованы целыми числами от $$$0$$$ до $$$10^9$$$. Обозначим за $$$(x, y)$$$ клетку, расположенную в строке $$$x$$$ в столбце $$$y$$$.

Давайте назовем клетку $$$(x, y)$$$ хорошей, если $$$x \& y = 0$$$, где $$$\&$$$ — это операция побитового И.

Давайте построим граф, вершинами которого будут все хорошие клетки и проведем ребра между всеми парами соседних по стороне хороших клеток. Можно доказать, что этот граф является деревом — связным графом без циклов. Давайте подвесим это дерево за вершину $$$(0, 0)$$$, таким образом мы получим корневое дерево с корнем $$$(0, 0)$$$.

Два игрока играют в игру. Изначально некоторые хорошие клетки черные, а остальные белые. Каждый игрок на своем ходе выбирает черную хорошую клетку и подмножество ее предков (возможно пустое) и инвертирует их цвета (с белого на черный и наоборот). Игрок, который не может сделать ход (потому что все хорошие клетки белые), проигрывает. Можно доказать, что эта игра конечна.

Изначально все клетки белые. Вам дано $$$m$$$ пар клеток. Для каждой пары клеток все клетки на простом пути между клетками в паре красятся в черный цвет. Обратите внимание, что эти цвета не инвертируются, а мы красим клетки в черный цвет.

Sohrab и Mashtali собираются сыграть в эту игру. Sohrab будет первым игроком, а Mashtali вторым.

Mashtali хочет победить и решил поступить нечестно. Он может сделать следующую операцию несколько раз перед тем как игра начнется: выбрать клетку и инвертировать цвета всех вершин на пути между ней и корнем дерева.

Mammad, который наблюдает за ними, задался вопросом: «какое минимальное количество операций должен сделать Mashtali, чтобы иметь выигрышную стратегию?».

Найдите ответ на этот вопрос для изначальной конфигурации цветов вершин дерева. Можно доказать, что хотя бы один способ поступить нечестно существует.