графы

Вы играете в свою любимую мобильную игру. Карта игры состоит из \(N\) \((2 \leq N \leq 10^5)\) комнат, помеченных \(1\dots N\) соединённых \(N-1\) ребрами так, что формируют дерево.

Вы можете исследовать карту, выполняя серию "путешествий". Путешествие это простой путь из комнаты \(1\) в любую другую комнату на дереве. Когда Вы заканчиваете одно путешествие, Вы можете начать другое снова из комнаты \(1\). Карта завершена, когда каждая из комнат посещена хотя бы одним путешествием. Ваша главная цель - завершить карту минимальным количеством путешествий.

Ваша вторая цель - собрать как можно больше зелий. Прежде чем начнутся путешествия, зелье появится в некоторой комнате. Вы можете взять зелье, посетив комнату, в которой появилось зелье перед текущим путешествием. Если Вы не возьмёте зелье, оно исчезнет, когда это путешествие закончится, и Вы не сможете взять его в будущем путешествии.

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

Фермер Джон имеет на своей ферме \(N\)(\(2 \leq N \leq 2\cdot 10^5\)) коров, последовательно пронумерованных \(1 \dots N\). Корова \(i\) расположена в целочисленных координатах \((x_i, y_i)\) (\(1\le x_i,y_i\le N\)). ФД хочет выбрать две команды для игры в мумбол.

Одна из команд будет "красная команда"; другая - "синяя". Имеется несколько требований к командам. Ни одна команда не будет пустая. Каждая из коров должна быть не более чем в одной команде (возможно ни в одной). Команды могут быть разделены горизонтальной или вертикальной прямой на плоскости с нецелочисленной координатой, например, \(x = 0.5\).

Помогите ФД. Вычислите количество способов составить пару из красной и синей команды, при выполнении вышеуказанных ограничений. Ответ выводить по модулю \(10^9+7\).

Беси проводит каникулы на сети из \(N\) (\(2\le N\le 10^4\)) островов помеченных \(1\dots N\) соединённых \(M\) двунаправленными мостами, каждый из которых соединяет два острова (\(N-1\le M\le 3/2(N-1)\)). Гарантируется, что эти мосты формируют простой граф (в частности, нет двух мостов, которые соединяют одну и ту же пару островов, и нет моста из острова в себя же).

Также гарантируется, ни один мост не лежит более чем в одном простом цикле. Цикл называется простым, если он не содержит повторяющиеся острова.

Беси начинает на острове \(1\) и путешествует в соответствии со следующей процедурой:

1. Если нет мостов, ведущих в соседние острова, по которым она ещё не ездила, она завершает путешествие.
2. Иначе, с вероятностью \(p_i\pmod{10^9+7}\) она завершает путешествие.
3. Иначе, из всех мостов на соседние острова, по которым она ещё не перемещалась, она равновероятно выбирает один и перемещается по нему.

Для каждого острова выведите вероятность, что она закончит своё путешествие именно на этом острове по модулю \(10^9+7\).

**Замечание: Память на тест 512MB, в два раза больше, чем по умолчанию.**

Беси планирует бесконечное путешествие в стране с \(N\) (\(1\leq N \leq 10^5\)) городами. В каждом городе есть портал и время зацикливания \(T_i\). Все \(T_i\). являются степенями двойки и \(T_1 + \cdots + T_N \leq 10^5\). Если Вы войдёте в портал города \(i\) в день \(t\), Вы немедленно выйдете из портала в городе \(c_{i, t\bmod{T_i}}\).

У Беси есть \(Q\) (\(1\leq Q \leq 5\cdot 10^4\)) планов её путешествия, каждый из которых есть тройка чисел \((v, t, \Delta)\). В каждом плане она начинает в городе \(v\) в день \(t\). Затем она делает следующее \(\Delta\) раз. Она входит в портал текущего города, затем ждёт один день. Для каждого из её планов она хочет узнать, в каком городе она закончит путешествие.

Теперь Беси занялась физикой. Она открыла пару субатомных частиц, которые назвала mootrinos и antimootrinos. Как стандартные пары материя-антиматерия, mootrinos и antimootrinos аннигилируют друг друга и исчезают, когда они встречаются. Ещё эти частицы отличаются тем, что они переключают направление движения (сохраняя скорость), когда Беси посмотрит на них.

В последнем эксперименте Беси разместила чётное число \(N\) (\(2 \leq N \leq 2 \cdot 10^5\)) частиц в ряд. Ряд начинается с mootrino слева и затем чередует два вида частиц, при этом \(i\)-ая частица расположена в позиции \(p_i\) (\(0 \leq p_1 < \cdots < p_N \leq 10^{18}\)). Mootrinos изначально движутся вправо, а antimootrinos изначально движутся влево. \(i\)-я частица движется со скоростью \(s_i\) единиц в секунду (\(1 \leq s_i \leq 10^9\)).

Беси ведёт наблюдение в следующие моменты времени:

• Сначала через \(1\) секунду после начала эксперимента.
• Затем через \(2\) секунды после первого наблюдения.
• Затем через \(3\) секунды после второго наблюдения.
• ...
• Затем через \(n + 1\) секунду после \(n\)-го наблюдения.

Этот эксперимент может потребовать слишком много времени для завершения, поэтому Беси для начала хочет просимулировать результаты. Помогите Беси определить, когда (т.e., номер наблюдения) когда она обнаружит, что исчезли все частицы. Можно доказать, что все частицы в конце концов исчезнут.

Молочная фабрика Фермера Джона может быть описана решёткой из \(N\) * \(N\) ячеек (\(1 \le N \le 1000\)), которые содержат конвейерные ленты. Позиция (\(a,b\)) описывает ячейку, которая находится в строке \(a\) сверху и столбце \(b\) слева. �меется \(5\) типов ячеек.

1. "L" — перемещает все элементы на 1 ячейку влево каждую единицу времени.
2. "R" — перемещает все элементы на 1 ячейку вправо каждую единицу времени.
3. "U" — перемещает все элементы на 1 ячейку вверх каждую единицу времени.
4. "D" — перемещает все элементы на 1 ячейку вниз каждую единицу времени.
5. "?" — ФД не построил ещё конвейерный двигатель в этой ячейке.

Заметим, что конвейеры могу перемещать элементы за решётку. Ячейка \(c\) является неиспользуемой если предмет, размещенный в ячейке \(c\) никогда не покинет решётку, он будет всегда двигаться внутри решётки.

�значально, ФД ещё не начал строить фабрику, поэтому все ячейки содержат "?". Для следующих \(Q\) (\(1 \le Q \le 2 \cdot 10^5\)) дней начиная со дня \(1\) и заканчивая днём \(Q\), , ФД выбирает свободную ячейку и строит в ней конвейер.

А именно, в течение \(i\)-го дня ФД строит конвейер типа \(t_i\) (\(t_i \in {\text{{L,R,U,D}}}\)) в позиции (\(r_i,c_i\)) (\(1 \le r_i,c_i \le N\)). Гарантируется, что конвейера нет в позиции (\(r_i,c_i\)).

После каждого дня помогите ФД найти минимальное количество неиспользованных ячеек, которое он может достичь, оптимально строя конвейеры во всех оставшихся свободных ячейках.

ПР�МЕР ВВОДА:

3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U

ПР�МЕР ВЫВОДА:

0
0
0
2
3

RL?
U??
?DL

Один оптимальный способ построить конвейер в оставшихся ячейках представлен ниже.

RLR
URR
LDL

ПР�МЕР ВВОДА:

3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D

ПР�МЕР ВЫВОДА:

0
2
2
4
4
6
6
9

RLD
D?U
URL

ПР�МЕР ВВОДА:

4 13
2 2 R
2 3 R
2 4 D
3 4 D
4 4 L
4 3 L
4 2 U
3 1 D
4 1 R
2 1 L
1 1 D
1 4 L
1 3 D

ПР�МЕР ВЫВОДА:

0
0
0
0
0
0
0
0
11
11
11
11
13

Автор: Alex Liang

Молочная фабрика Фермера Джона может быть описана решёткой из \(N\) * \(N\) ячеек (\(1 \le N \le 1000\)), которые содержат конвейерные ленты. Позиция (\(a,b\)) описывает ячейку, которая находится в строке \(a\) сверху и столбце \(b\) слева. �меется \(5\) типов ячеек.

1. "L" — перемещает все элементы на 1 ячейку влево каждую единицу времени.
2. "R" — перемещает все элементы на 1 ячейку вправо каждую единицу времени.
3. "U" — перемещает все элементы на 1 ячейку вверх каждую единицу времени.
4. "D" — перемещает все элементы на 1 ячейку вниз каждую единицу времени.
5. "?" — ФД не построил ещё конвейерный двигатель в этой ячейке.

Заметим, что конвейеры могу перемещать элементы за решётку. Ячейка \(c\) является неиспользуемой если предмет, размещенный в ячейке \(c\) никогда не покинет решётку, он будет всегда двигаться внутри решётки.

�значально, ФД ещё не начал строить фабрику, поэтому все ячейки содержат "?". Для следующих \(Q\) (\(1 \le Q \le 2 \cdot 10^5\)) дней начиная со дня \(1\) и заканчивая днём \(Q\), , ФД выбирает свободную ячейку и строит в ней конвейер.

А именно, в течение \(i\)-го дня ФД строит конвейер типа \(t_i\) (\(t_i \in {\text{{L,R,U,D}}}\)) в позиции (\(r_i,c_i\)) (\(1 \le r_i,c_i \le N\)). Гарантируется, что конвейера нет в позиции (\(r_i,c_i\)).

После каждого дня помогите ФД найти минимальное количество неиспользованных ячеек, которое он может достичь, оптимально строя конвейеры во всех оставшихся свободных ячейках.

ПР�МЕР ВВОДА:

3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U

ПР�МЕР ВЫВОДА:

0
0
0
2
3

RL?
U??
?DL

Один оптимальный способ построить конвейер в оставшихся ячейках представлен ниже.

RLR
URR
LDL

ПР�МЕР ВВОДА:

3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D

ПР�МЕР ВЫВОДА:

0
2
2
4
4
6
6
9

RLD
D?U
URL

ПР�МЕР ВВОДА:

4 13
2 2 R
2 3 R
2 4 D
3 4 D
4 4 L
4 3 L
4 2 U
3 1 D
4 1 R
2 1 L
1 1 D
1 4 L
1 3 D

ПР�МЕР ВЫВОДА:

0
0
0
0
0
0
0
0
11
11
11
11
13

Автор: Alex Liang

У Фермера Джона есть блок сыра в форме куба. Он лежит в трёхмерном пространстве от точки \((0,0,0)\) до точки \((N, N, N)\) (\(2 \leq N \leq 1000\)). ФД выполняет серию из \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) операций над своим блоком сыра.

В каждой операции ФД вырезает блок размером \(1\) * \(1\) * \(1\) из сыра от целых координат \((x, y, z)\) до \((x+1, y+1, z+1)\), где \(0\le x,y,z<N\). Гарантируется, сыр есть в этом месте. Поскольку ФД играет в Moocraft гравитация не вызывает падение блоков сыра при вырезании.

После каждой операции выведите количество различных способов, которыми ФД может вставить блок \(1\) * \(1\) * \(N\) так, что ни одна часть блока не перекрывается с оставшимся сыром. Каждая вершина блока должна иметь целочисленные координаты в интервале \([0,N]\) по всем трём осям. ФД может вращать блок как он хочет.

Изначально среди \(N\) коров ФД есть пары друзей \(N-1\). (\(2\le N\le 2\cdot 10^5\)) коровы, помеченные \(1\dots N\), образуют дерево. Коровы один за другим покидают ферму в отпуск. В день \(i\) с фермы уходит \(i\)ая корова. ферме, а затем все пары друзей \(i\)-й коровы, все еще присутствующие на ферме становятся друзьями.

Для каждого \(i\) от \(1\) до \(N\), непосредственно перед уходом \(i\)-й коровы, ответьте сколько существуют таких упорядоченных троек различных коров \((a,b,c)\), что ни одна из \(a,b,c\) не в отпуске, \(a\) дружит с \(b\), а \(b\) дружит с \(c\)?

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

В частности, операция слияния берет любые два различных узла в дереве с один и тем же родителем и объединяет их в один узел со значением, равным максимальному значений двух объединенных узлов, а потомки — объединение всех потомков объединенных узлов (если есть).

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

Учитывая ее начальное и конечное деревья, определите последовательность операций слияния, которые могла бы выполнить Бесси. Гарантируется, что последовательность существует.

Каждый вход состоит из \(T\) (\(1\le T\le 100\)) независимых подтестов. Гарантируется, что сумма \(N\) по всем тестам не превышает \(1000\).

Из-за неорганизованной структуры его амбара, фермер Джон решил навести порядок в стойлах.

В каждом амбаре есть \(N\) стойл, помеченных от \(1\) до \(N\) (\(1 \le N \le 10^5\)) и \(M\). (\(0 \le M \le 10^5\)) двунаправленных коридоров, соединяющих пары стойл друг с другом. \(i\)-ое стойло окрашено в цвет \(C_i\) и изначально имеет единственный ключ цвета \(S_i\) в нем. ФД придется переносить ключи, чтобы успокоить коров и навести порядок в стойлах.

ФД начинает игру в стойле \(1\), не держа никаких ключей, и ему разрешено несколько раз сделать один из следующих ходов:

• Взять ключ в стойле, в котором он сейчас находится. ФД может держать несколько ключей одновременно. раз.
• Положить ключ, который он держит, в стойло, в котором он сейчас находится. В стойле может находиться несколько ключей одновременно.
• Войти в стойло \(1\), начав движение.
• Войти в стойло, отличное от стойла \(1\), перемещаясь по коридору. Он может сделать это только в том случае, если он в настоящее время держит ключ, который того же цвета, что и стойло, в которое он входит.

К сожалению, кажется, что ключи находятся не на своих местах. Чтобы восстановить порядок в амбаре \(i\)-ое стойло требует, чтобы в нём находился один ключ и он имел цвет \(F_i\). Гарантируется, что \(S\) является перестановкой \(F\).

Для \(T\) разных амбаров (\(1\le T\le 100\)) ФД стартует в стойле \(1\) и должен поместить каждый ключ в соответствующее место и вернуься обратно в стойло \(1\). Для каждого из \(T\) амбаров, пожалуйста, ответьте, возможно ли это сделать.

ОБРАЗЕЦ ВВОДА:

2

5 5
4 3 2 4 3
3 4 3 4 2
2 3 4 4 3
1 2
2 3
3 1
4 1
4 5

4 3
3 2 4 1
2 3 4 4
4 2 3 4
4 2
4 1
4 3

Беси работает в новейшем текстовом редакторе miV!. Она начинает со входной строки, состоящей исключительно из больших и маленьких английских букв и хочет преобразовать её в некоторую другую строку. Одним кликом miV! позволяет ей заменить все вхождения одной английской буквы \(c_1\) в строке на другую английскую букву \(c_2\). Например, если дана строка string \(\texttt{aAbBa}\) и \(c_1\) есть 'a' и \(c_2\) есть 'B', то строка трансформируется в \(\texttt{BAbBB}\).

Для каждого из \(T\) (\(1\le T\le 10\)) независимых тестов, определите минимальное количество кликов, которое требуется, чтобы преобразовать входную строку в желаемую выходную.

**Замечание: Время на тест в этой задаче 4s, в два раза больше чем по умолчанию. Ограничение по памяти для этой задачи 512MB, в два раза больше чем по умолчанию.**

У Фермера Джона \(N\) (\(2\le N\le 2\cdot 10^5\)) тракторов, где -ый трактор может использоваться только в интервале \([l_i,r_i]\) включительно. Интервалы для тракторов имеют левые конечные точки \(\ell_1<\ell_2<\dots<\ell_N\) и правые конечные точки \(r_1<r_2<\dots<r_N\). Некоторые из тракторов специальные.

Два трактора \(i\) и \(j\) называются соседними если \([\ell_i,r_i]\) и \([\ell_j,r_j]\) пересекаются. ФД может перебраться (выполнить трансфер) с одного трактора на любой соседний трактор. Путь между двумя тракторами \(a\) и \(b\) состоит трансферов таких, что первый трактор в последовательности есть \(a\), последний трактор в последовательности есть \(b\) и каждые два трактора в последовательности соседние. Гарантируется ,что имеется путь из трактора \(1\) в трактор \(N\). Длина пути - количество трансферов (или эквивалентно, количество тракторов минус один).

Вам даётся \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов, каждый указывает пару тракторов \(a\) и \(b\) (\(1\le a<b\le N\)). Для каждого запроса выведите два целых числа:

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

**Замечание: время на тест в этой задаче 4сек, в два раза больше чем по умолчанию.**

Кто-то пасётся в \((1 \le G \le 10^5)\) частных садах Фермера Джона. ФД может определить точное время, когда кто-то пасётся на каждом пастбище. Он также установил, что каждый раз это делает одна корова.

Чтобы отвести от себя подозрения, каждая из \(N\) \((1 \le N \le 10^5)\) коров ФД должна предъявить алиби, которое доказывает, что корова была в конкретном месте в указанное время. Помогите ФД проверить эту информацию.

Корова будет определена как невиновная, если невозможно ей пройти все пастбища и алиби. Корова перемещается на единицу расстояния за единицу времени.

Имеется \(N\) пастбищ (\(2 \le N \le 2\cdot 10^5\)), соединённых \(N-1\) дорогой, так что ои образуют дерево. Перемещение по каждой дороге занимает одну секунду. В начале на каждом пастбище 0 травы, трава на \(i\)-ом пастбище растёт со скоростью \(a_i\) (\(1\le a_i\le 10^8\)) единиц в секунду. Фермер Джон вначале находится в пастбище 1 и должен удобрить траву на каждом пастбище. Если он посещает пастбище, в котором \(x\) единиц травы, он должен потратить \(x\) единиц удобрений. Удобрять требуется только при первом посещении пастбища и удобрение пастбища занимает 0 единиц времени.

Ввод содержит дополнительный параметр \(T\in \{0,1\}\).

• Если \(T=0\), ФД должен завершить путь в пастбище 1.
• Если \(T=1\), ФД может завершить путь в любом пастбище.

Вычислите минимальное количество времени, которое требуется ФД, чтобы удобрить все пастбища и минимальное количество удобрений, которое потребуется, чтобы закончить в этот момент времени.

У Фермера Джона \(N\) амбаров (\(3\le N\le 5\cdot 10^5\)), из которых \(K\) (\(3\le K\le N\)) различных пар амбаров соединены.

Сначала Анабель назначила каждому амбару различную цифровую метку в интервале \([1,N]\), и заметила, что амбары с метками \(a_1,\dots,a_K\) соединены в цикл, в этом порядке. То есть, амбары \(a_i\) и \(a_{i+1}\) соединены для всех \(1\le i<K\), и амбары \(a_K\) и \(a_1\) также соединены. Все \(a_i\) различны.

Затем Беси также назначила каждому амбару различную цифровую метку в интервале \([1,N]\) и заметила, что амбары с метками \(b_1,\dots,b_K\) соединены в цикл, в таком порядке. Все \(b_i\) различны.

Некоторым (возможно никаким или всем) амбарам Анабель и Беси назначили одинаковые метки. Вычислите максимально возможное количество амбаров, которым Анабель и Беси назначили одинаковые метки.

У Фермера Джона есть \(N\) (\(2\le N\le 10^5\)) коров, помеченных \(1\dots N\), где соединения между коровами описываются деревом. К несчастью, начала распространяться болезнь.

Изначально, инфицированы несколько коров. Каждую ночь инфицированная корова передаёт болезнь своим соседям. Однажды инфицированная корова остаётся инфицированной. После некоторого количества ночей ФД протестировал своих коров на наличие болезни. И про каждую узнал больна она или нет.

Вам даны \(Q\) (\(1\le Q\le 20\)) различных значений количества ночей - каждое - целое число в интервале \([0,N]\). Для каждого количества ночей определите минимальное количество коров, которые были изначально инфицированы или укажите, что количество ночей не соответствует информации об инфицированных коровах.

Беси столкнулась со сложной задачей на графы - помогите ей.

Вам дан связный, ненаправленный граф с вершинами, помеченными \(1\dots N\) и рёбрами помеченными \(1\dots M\) (\(2\le N\le 2\cdot 10^5\), \(N-1\le M\le 4\cdot 10^5\)). Для каждой вершины \(v\) в этом графе выполняется следующий процесс:

1. Пусть \(S=\{v\}\) и \(h=0\).
2. While \(|S|<N\),
   1. �з всех ребер, которые имеют \(S\) как конечную точку, пусть \(e\) - ребро с минимальной меткой
   2. Добавляем в \(S\) конечную точку ребра \(e\), которая не содержится в \(S\).
   3. Устанавливаем \(h=10h+e\).
3. Возвращаем \(h\pmod{10^9+7}\).

ПР�МЕР ВВОДА:

3 2
1 2
2 3

ПР�МЕР ВЫВОДА:

12
12
21

ПР�МЕР ВВОДА:

5 6
1 2
3 4
2 4
2 3
2 5
1 5

ПР�МЕР ВЫВОДА:

1325
1325
2315
2315
5132

Рассмотрим старт в вершине \(i=3\). Сначала мы выберем ребро \(2\), после чего \(S = \{3, 4\}\) и \(h = 2\). Далее мы выберем ребро \(3\), после чего \(S = \{2, 3, 4\}\) и \(h = 23\). Затем мы выберем ребро \(1\), после чего \(S = \{1, 2, 3, 4\}\) и \(h = 231\). Наконец мы выберем ребро \(5\), после чего \(S = \{1, 2, 3, 4, 5\}\) и \(h = 2315\). Поэтому ответ для \(i=3\) есть \(2315\).

ПР�МЕР ВВОДА:

15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15

ПР�МЕР ВЫВОДА:

678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081

Ответ выводите по модулю \(10^9+7\).

Problem credits: Benjamin Qi

Беси собирается в путешествие по Cowland, которая имеет \(N\) (\(2\le N\le 2\cdot 10^5\)) городов, пронумерованных от \(1\) до \(N\) и \(M\) (\(1\le M\le 4\cdot 10^5\)) односторонних дорог. \(i\)-ая дорога ведёт из города \(a_i\) в город \(b_i\) и имеет метку \(l_i\) (\(1\le a_i,b_i\le N\), \(1\le l_i\le 10^9\)).

Путешествие длины \(k\) начинается в городе \(x_0\) - это последовательность городов \(x_0, x_1, \ldots, x_k\), таких, что что существует дорога из города \(x_i\) в город \(x_{i+1}\) для всех \(0\le i < k\). Гарантируется, что не существует путешествий бесконечной длины, и что никакие две дороги не соединяют одну и ту же пару городов.

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

Выведите длину и сумму меток дорог, предпочитаемого Беси путешествия, начинающегося из каждого города.

Беси недавно узнала, что её любимая исполнительница Эльза Свифт отправилась в концертный тур. Однако билеты продали так быстро, что Беси планирует полететь в другой город, чтобы посетить концерт. Тур пройдёт в \(N\) (\(2\le N\le 750\)) городах, помеченных \(1\dots N\), и для каждой пары городов \((i,j)\) где \(i<j\) или существует прямой перелёт из \(i\) в \(j\) или нет.

Полётный маршрут из города \(a\) в город \(b\) (\(a<b\)) это последовательность из \(k\ge 2\) городов \(a=c_1<c_2<\dots<c_k=b\) таких, что для каждого \(1\le i<k\), существует прямой перелёт из города \(c_i\) в город \(c_{i+1}\). Для каждой пары городов \((i,j)\) где \(i<j\), Вам задана четность количества полетных маршрутов между ними (0 для чётных, 1 для нечётных).

Беси хочет узнать, сколько пар городов имеет прямые перелёты между ними. Можно доказать, что ответ определяется уникально.