поиск в глубину и подобное

ФД начинает в позиции \((0,0)\) и делает \(N\) шагов, двигаясь каждый раз на Единицу расстояния на север, юг, восток или запад. Каждый раз, когда он делает шаг, он строит изгородь за собой. Например, если первый его шаг будет на север, он добавит сегмент изгороди от \((0,0)\) до \((0,1)\). ФД может посещать точки повторно много раз и даже может строить одни и те же отрезки изгороди много раз. Его изгородь может даже пересекать себя много раз.

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

Определите минимальное количество дверей которые требуется построить, так чтобы каждый регион был доступен из каждого другого региона.

Беси собирается в путешествие по 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\) полей (\(1 \leq N \leq 2 \cdot 10^5\)), последовательно пронумерованных \(1 \ldots N\), и удобно соединённых множеством из \(M\) двунаправленных тропинок (\(1 \leq M \leq 2 \cdot 10^5\)). Будучи "существами привычки" коровы используют одно множество из \(N-1\) тропинок для всех своих ежедневных перемещений между полями. Они называют эти тропинки "стандартными" тропинками. Возможно добраться от любого поля до любого другого поля, используя только стандартные тропинки.

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

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

Амбар может быть представлен прямоугольной решёткой \(N \times M\). В некоторых ячейках решётки находится сено. Беси находится в одной ячейке этой решётки, а большой деревянный ящик занимает другую. Беси и этот ящик не помещаются в одной ячейке одновременно, также они не могут заходить в ячейку с сеном.

Бесси может двигаться в 4 ортогональных направлениях (север, юг, запад, восток). пока не уткнётся в ячейку с сеном. Если она попытается войти в ячейку с ящиком, то ящик продвинется на одну ячейку в этом же направлении, если там есть свободная ячейка. Если свободной ячейки нет, Беси не может сдвинуть ящик.

Определённая ячейка решётки указана как цель. Беси должна доставить ящик в это место.

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

Замечание: в этой задаче можно использовать 512 Мбт оперативной памяти, в отличие от лимита по умолчанию в 256 Мбт.

В попытке улучшить управленческую структуру в компании, коровы структурировали её в виде двоичного дерева, где каждый сотрудник отвечает за управление своим двумя непосредственными подчинёнными " левым " и " правым ". Кроме того, для того чтобы сбалансировать нагрузку на каждого работника, коровы организовали структуру дерева так, чтобы для каждого сотрудника E, общее количество сотрудников в левом поддереве E было равно или больше чем количество сотрудников в правом поддереве.

Каждый сотрудник имеет уникальной ID - число в диапазоне \(1\ldots N\), с корнем дерева - сотрудником номер 1. Вы можете интерактивно запрашивать у сотрудника ID двух его подчинённых. Это делается выводом ID этого сотрудника в стандартный вывод, за которым следует перевод строки. В ответ Вы получите одну строку, которая содержит два целых числа - ID левого и правого подчинённых данного сотрудника. Оба этих числа могут быть равны 0, если у него нет ни одного подчинённого. Или только второе число может быть 0, если у него нет правого подчинённого. (Заметим, в что в соответствии с правилом балансирования, левое поддерево всегда больше или равно правом, и потому не возможна ситуация, когда у сотрудника есть правый подчинённый, но нет левого подчинённого).

К несчастью, коровы потеряли точное значение \(N\) Пожалуйста, вычислите это число и выведите "Answer N", а за ним перевод строки как последнюю строку вашего вывода. Ваша программа имеет право сделать не более 70,000 запросов и не может выполняться боле 4 секунд (8 для Java и Python).

Далее приведен пример возможного взаимодействия между Вашей программой и грейдером (оценивающей программой).

YOUR PROGRAM: 1
GRADER: 4 3
YOUR PROGRAM: 4
GRADER: 2 0
YOUR PROGRAM: 3
GRADER: 0 0
YOUR PROGRAM: Answer 4

Дерево, соответствующее этому взаимодействию

     1
   4   3
 2

Заметим, что нет необходимости спрашивать о детях для узла 2, поскольку мы можем логически вывести, что у него нет детей из того факта, что у вершины 4 нет правого потомка.