Город будущего застроен небоскребами, для передвижения между которыми и парковки транспорта многие тройки небоскребов соединены треугольной подушкой из однополярных магнитов. Каждая подушка соединяет ровно 3 небоскреба и вид сверху на нее представляет собой треугольник, с вершинами в небоскребах. Это позволяет беспрепятственно передвигаться между соответствующими небоскребами. Подушки можно делать на разных уровнях, поэтому один небоскреб может быть соединен различными подушками с парами других, причем два небоскреба могут соединять несколько подушек (как с разными третьими небоскребами, так и с одинаковым). Например, возможны две подушки на разных уровнях между небоскребами 1, 2 и 3, и, кроме того, магнитная подушка между 1, 2, 5.

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

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

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

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

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

Таким образом, каждым очередным ходом игрок может переместить автобус на любую соседнюю по стороне свободную клетку, кроме той, с которой автобус только что приехал. (Первым ходом можно переместить автобус в любую сторону.)

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

Строго говоря, пусть игрок перемещает автобус бесконечно долго (т.е. в течение бесконечного количества ходов). Тогда несложно видеть, что в некоторых свободных клетках игрок может бывать бесконечно много раз (при условии, что начальная клетка выбрана удачно), а в некоторых — не более одного (и то лишь в начальной части игры).

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

В Якутске \(n\) домов. Некоторые из них соединены дорогами с односторонним движением.

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

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

Ваша задача — написать программу, рассчитывающую оптимальное положение станций.

В секретном 240 отделе ИПФ РАН \(N\) сотрудников и \(N\) компьютеров. В отделе вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого сотрудника будут определены ровно \(K\) компьютеров, к которым этот сотрудник будет иметь допуск (т.е. за которыми этот сотрудник будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно \(K\) сотрудников.

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

Обратите внимание, что значение \(K\) тоже будет известно лишь в последний момент. Из общих соображений секретности известно лишь, что \(K\) будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений \(K\).