Однажды в далекой-далекой стране правительство создало Министерство по сокращению бумажной волокиты. Как вы наверное догадались, это было крупнейшее министерство за всю историю страны. Количество сотрудников было поистине огромным. Несмотря на это, структура министерства была очень простой: каждый сотрудник имел не более трёх подчинённых, каждый из которых снова имел не более трех подчиненных и так далее...

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

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

Есть два особых случая:

• Департамент, в котором должностное лицо  — сам министр, тогда этот департамент есть всё министерство.

• Департамент, в котором у должностного лица нет ни одного подчинённого.

Высотой департамента назовем длину максимальной последовательность сотрудников x ₁ , ..., x _d такую, что сотрудник x _i является начальником сотрудника x _{i + 1} для всех 1 ≤ i < d . Заметим что высота департамента, состоящего из одного сотрудника равна 1 .

Два департамента A и B совпадают, если существует взаимно-однозначное отображение, сопоставляющее каждому сотруднику x _A из департамента A сотрудника x _B из департамента B , таким образом, что сотрудник x _A является начальником сотрудником y _A , тогда и только тогда, когда x _B является начальником y _B . Заметим, что если два департамента совпадают, то они имеют одинаковую высоту, одинаковое количество сотрудников и начальнику первого департамента соответствует начальник второго.

На приведенных картинках департаменты A и B совпадают, а C не совпадает ни с A , ни c B .

Вам необходимо для каждой высоты вычислить количество различных департаментов имеющих такую глубину. Формально требуется построить последовательность n ₁ , ..., n _d , где d это высота всего министерства, а n _i — количество различных департаментов высоты i .

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

Инопланетяне предпочитают строить здания на тех реках, берега которых представляют из себя параллельные прямые, поэтому область реки, где будут строить инопланетяне, можно себе представить как прямоугольную таблицу W × H , у которой каждая клеточка имеет координаты ( X , Y ). Каждая клеточка пропускает через себя 1 кубический метр воды в секунду, и вода может перетекать только между клеточками соседним по стороне. Каждая клеточка на южной стороне реки ( Y = 0 ) имеет приток воды из реки в размере 1 кубический метр воды в секунду. Каждый дом в поселке занимает прямоугольник, состоящий из единичных клеточек; если в клеточке стоит дом, то вода через нее протекать не может. Ваша задача — вычислить, сколько кубических метров за секунду пропускает поселок инопланетян. То есть сколько кубических метров воды вытекает из всех северных клеток поселка ( Y = H - 1 ) в сумме.

Как известно, вода несжимаема, то есть не может накапливаться в клетке, соответственно если в клетку втекло сколько-то воды, то столько же должно и вытечь.

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

До недавнего времени в Исоле не было автобусного сообщения. В срочном порядке была основана первая автобусная компания «Коррейра», и решено проложить по автобусному маршруту между каждой парой островов. Поскольку между некоторыми островами не существует пути по мостам, между такими островами решено маршрут не создавать.

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