Вова и Марина любят играть в игры, а особенно — придумывать к ним свои правила. Недавно они открыли для себя веселую игру «Чапаев», в которой игроки должны сбивать щелчками шашки вражеского цвета с шахматной доски (также эта игра известна под названием «Щелкунчики»). Вдоволь наигравшись, они решили модифицировать правила, добавив игре математическую сложность.

Теперь они играют в «Чапаева» не на шахматной доске, а на доске в форме дерева! Их дерево состоит из \(N\) вершин. Вершина 1 является корнем дерева, а из каждой из оставшихся вершин проведено ребро в некоторую вершину с меньшим номером — ее непосредственного предка.

В игре участвуют шашки одного цвета, изначально расположенные в некоторых вершинах дерева. За один ход игрок выбирает некоторую шашку и щелчком отправляет ее к корню по ребрам дерева, сбивая при этом с доски все встреченные на пути шашки. Сама шашка, по которой производился удар, после попадания в корень дерева также слетает с доски.

Игроки делают ходы по очереди. Проигрывает тот игрок, к ходу которого на доске не остается шашек.

Придуманная ими игра замечательна также тем, что на одной и той же доске можно играть, начиная с разных начальных позиций шашек. Практика показала, что самые интересные партии получаются, если исходно расставить фишки во все вершины, являющиеся потомками (непосредственными или косвенными) некоторой вершины Root, при этом в саму вершину Root фишка не ставится.

Дети решили сыграть \(N\) партий, перебрав в качестве вершины Root каждую вершину дерева по одному разу. Если у очередной вершины Root нет потомков, и на доске исходно не оказывается ни одной фишки, то игры не происходит, и дети переходят к следующей расстановке. В каждой партии Марина ходит первой.

Вова интересуется у вас, в скольких партиях Марина сможет одержать победу, если игроки будут действовать оптимально.

Комментарий

Разберем тест из условия. Доска для игры показана на рисунках ниже. Дети сыграют четыре партии, выбирая в качестве Root вершины 1, 2, 3 и 5. Если выбрать в качестве Root любую из трех оставшихся вершин, на доске исходно не окажется ни одной фишки, поэтому игры не произойдет.

Если выбрать в качестве Root вершину 5, фишки будут исходно находиться в вершинах 6 и 7. В такой партии Марина проигрывает: после того, как она сбивает любую из этих двух фишек с доски, Вова сбивает оставшуюся и заканчивает партию.

Если выбрать в качестве Root вершину 2 или 3, у Марины будет возможность выиграть игру за один ход, щелкнув по фишке из вершины 4 (при этом, в случае Root = 2, она по пути также собьет фишку из 3 вершины по правилам игры)

Можно убедиться, что если выбрать в качестве Root вершину 1, у Марины также будет выигрышная стратегия. Для этого первым ходом Марина должна сбить фишку из вершины 2. Пример партии с таким начальным расположением показан ниже.

Таким образом, Марина выигрывает в трех партиях

08.03.2014, Париж, Франция. Дерзкое ограбление совершено в Парижском музее современного искусства. Похищено множество экспонатов, наиболее известный из которых — картина «Пиксели торжествуют» киберкубиста Этьена Бурсье-Мужено.

«Это большая потеря для нас, — заявил директор музея Фабрис Эрготт. — Полиция уже разыскивает преступников, но мы вынуждены признать, что, судя по тому, как легко злоумышленники справились с охранной системой, мы имеем дело с профессионалами экстра-класса и не питаем надежд на возвращение шедевра в нашу коллекцию. Кроме того, уничтожена вся база данных музея, поэтому реставраторы не обладают достаточным количеством информации для восстановления картины. Безусловно, каждый образованный француз знает, что она представляет собой прямоугольник из \(H\) x \(W\) черных и белых квадратных пикселей (\(H\) — высота, а \(W\) — ширина картины в пикселях). Но информацию о цвете самих пикселей придется добывать по крупицам».

В свою очередь, представитель Национального архива Франции Армель Ле Гофф поспешила успокоить культурную общественность: «К счастью, архив располагает снимками отдельных фрагментов картины. А именно, в нашем распоряжении имеется информация о \(N\) прямоугольных фрагментах (со сторонами, параллельными соответствующим сторонам картины), для каждого из которых известны его координаты \(r_1\), \(c_1\), \(r_2\), \(c_2\), а также цвета входящих в него пикселей. Строки картины пронумерованы от 1 до \(H\) сверху вниз, столбцы — от 1 до \(W\) слева направо, (\(r_1\); \(c_1\)) — номера строки и столбца левого верхнего пикселя фрагмента, (\(r_2\); \(c_2\)) — номера строки и столбца правого нижнего пикселя фрагмента, \(r_1\) ≤ \(r_2\), \(c_1\) ≤ \(c_2\). Однако, в силу ряда причин некоторые фрагменты могут храниться в инвертированном виде, то есть все белые пиксели в них заменены на черные, а все черные — на белые, при этом достоверно не известно, какие фрагменты инвертированы. Это серьезно усложняет задачу по восстановлению утерянного шедевра величайшего киберкубиста, поэтому мы обращаемся за помощью ко всему программистскому сообществу. Национальный архив, со своей стороны, готов предоставить все имеющиеся данные о фрагментах картины. Мы отдаем себе отчет в том, что, возможно, картину не удастся восстановить однозначно, поэтому просим найти максимально светлую из всех возможных подходящих картин, то есть содержащую как можно больше белых пикселей: широко известно, что „Пиксели“ являются одним из самых оптимистичных творений Этьена Бурсье-Мужено».

Комментарий

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

2 3
3
1 1 1 2
0 1
1 2 2 2
0
1
1 3 2 3
1
1

5
0 1 0 
0 0 0 

2 3
2
1 2 2 3
0 1
1 0
1 1 1 3
0 1 1

-1