Алгоритмы на графах

У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.

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

Входные данные
В первой строке содержится число N — количество свинок-копилок (1≤N≤100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

Выходные данные
Выведите единственное число: минимальное количество копилок, которые необходимо разбить.

Примечание
Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.
Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.
 

Зал супермаркета имеет форму прямоугольника размером M x N, в котором расставлены витрины размером 1 x 1. Стороны витрин параллельны стенам супермаркета, а расстояния от витрин до стен – целые числа.

В супермаркет привезли новую супервитрину размером K  x 1 и выгрузили в одном из углов супермаркета. Требуется передвинуть ее в противоположный угол супермаркета. При этом ее нельзя поворачивать, а можно лишь передвигать параллельно стенам супермаркета. Напишите программу, которая по плану супермаркета поможет определить, какое наименьшее количество витрин нужно убрать, чтобы передвинуть супервитрину.




Входные данные
В первой строке вводятся три натуральных числа M, N и K (M, N ≤ 100, K ≤ M). Начальное и конечное расположение супервитрины такие, как указано на верхнем рисунке. В следующей строке записано целое неотрицательно число V – количество витрин (0 ≤ V ≤ N*M). В следующих V строках входных данных содержатся различные пары целых неотрицательных чисел, характеризующие положения витрин. Первое число (от 0 до M–1) – расстояние от левой стены супермаркета до витрины, второе (от 0 до N–1) – расстояние от нижней стены до витрины (см. нижний рисунок). Гарантируется, что там, где изначально поставили супервитрину, других витрин нет.

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

U – на 1 вверх,
D – на 1 вниз,
L – на 1 влево,
R – на 1 вправо.
Количество символов в строке не должно превышать N x M
.

Если возможных маршрутов несколько, то выведите любой из них.

Родители подарили Пете набор детских кубиков. Поскольку Петя скоро пойдет в школу, они купили ему кубики с буквами. На каждой из шести граней каждого кубика написана буква.

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

Дан набор кубиков и имя сестры. Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики.

Входные данные
В первой строке вводится число N (1 <= N <= 100) - количество кубиков в наборе у Пети. Во второй строке задано имя Петиной сестры - слово, состоящие только из больших латинских букв, не длиннее 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.

Выходные данные
В первой строке выведите "YES" если выложить имя Петиной сестры данными кубиками можно, "NO" в противном случае.

В случае положительного ответа, во второй строке выведите M различных чисел из диапазона 1…N, где M - количество букв в имени Петиной сестры. i-е число должно быть номером кубика, который следует положить на i-е место при составлении имени Петиной сестры. Кубики нумеруются с 1, в том порядке, в котором они заданы во входных данных. Если решений несколько, выведите любое. Разделяйте числа пробелами.

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

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

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

Входные данные
В первой строке вводится число n
 - количество дырок (2 <= n <= 1000). Следующие n строк содержат по два целых числа - координаты дырок. Координаты не превышают 10⁴
 по абсолютной величине.

Выходные данные
В первой строке выведите k
 - количество различных расстояний, которые Дима мог установить между иглами измерителя. Следующие k строк должны содержать искомые расстояния, по одному вещественному числу в строке. Расстояния должны быть выведены в возрастающем порядке. Каждое число должно быть выведено с точностью не менее, чем 10^-9.

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

У Пети в саду растет яблоня. Воодушевленный историей об Исааке Ньютоне, который, как известно, открыл закон всемирного тяготения после того, как ему на голову упало яблоко, Петя с целью повысить свою успеваемость по физике часто сидит под яблоней.

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

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

Выясните, какие яблоки упадут с Петиной яблони.

Входные данные
В первой строке вводится число N - количество яблок на Петиной яблоне (1 <= N <= 200). Следующие N строк содержат описания яблок. Будем считать все яблоки шарами. Каждое яблоко задается координатами своей самой верхней точки (той, где оно исходно прикреплено к дереву, длиной черенка пренебрежем) x_i, y_i и z_i и радиусом r_i ( -10000 <= x_i, y_i, z_i <= 10000, 1 <= r_i <= 10000, все числа целые). Гарантируется, что изначально никакие яблоки не пересекаются (даже не соприкасаются). Ось OZ направлена вверх.

Выходные данные
В первой строке выведите количество яблок, которые упадут с яблони, если начнет падать первое яблоко. В следующей строке выводите номера упавших яблок. Яблоки нумеруются, начиная с 1, в том порядке, в котором они заданы во входных данных.

K участникам сборов для решения было предложено K задач. Участники решили разделить задачи между собой, решить каждому по одной задаче, а затем обменяться решениями (они не учли, что система ejudge способна отследить данный факт J). Известно ориентировочное время, за которое каждый из участников сборов может решить каждую из предложенных задач.

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

Входные данные
Во входном файле сначала записано число K (0 < K < 101) и далее K2 неотрицательных целых чисел, не превосходящие 20000, описывающих матрицу K x K, времен решения каждым из участников каждой из задач.

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

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

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

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

	4 станции, 3 перегона: 1-4, 2-4, 3-4 Маршруты: 1-4-2, 2-4-3, 3-4-1.   Ответ: решения нет
	5 станций, 4 перегона: 1-5, 2-5, 3-5, 4-5 Маршруты: 1-5-2, 2-5-3, 3-5-4, 4-5-1.   Ответ: решение есть; например, следующее: номер станции: 1 2 3 4 5 тарифный номер: 1 4 1 5 3   Замечание: тарифные номера разных станций могут совпадать.

Формат входных данных

В первой строке входных данных содержатся два целых числа: N — количество станций (2 ≤ N ≤ 100 000), и M — количество перегонов между ними (1 ≤ M ≤ N – 1). В последующих M строках записаны пары целых чисел a, b (a ≠ b, 1 ≤ a ≤ N, 1 ≤ b ≤ N), означающие наличие перегона между станциями a и b. За ними в отдельной строке записано единственное целое положительное число K — количество маршрутов электричек. В последующих K строках идут описания маршрутов электричек, по одному на строке. Каждое описание представляет собой последовательность целых чисел — номеров всех станций маршрута в порядке одного из двух возможных направлений следования электрички. Описание маршрута заканчивается числом 0.

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

Формат выходных данных 

В первую строку выведите «NO», если искомого назначения тарифных номеров не существует. В противном случае в первую строку выведите «YES», а в следующей строке — N целых положительных чисел, где i-е число — тарифный номер i-й станции. Тарифный номер каждой станции должен находиться в диапазоне от 1 до N.

Если существует несколько решений, необходимо вывести любое из них.

Вася из задачи A по-прежнему занят поиском кладов. Более того, у него появились последователи. Один из таких последователей попросил Васю помочь в своих поисках. Так, по карте сокровищ Васю просят восстановить кратчайший путь до клада. Конфигурация лабиринта совпадает с конфигурацией, описанной в задаче A (поле \(N \times M (1 \le N, M \le 100, N \times M \le 100))\), в одной клетке которого находится клад, в K
 клетках находятся входы в лабиринт).

Требуется вывести искомый путь.

Формат входных данных
Первая строка содержит 2 числа N<=100 и M<=100, задающие размеры лабиринта. Далее следует описание лабиринта: N
 строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
В (N+2)-й строке находится число \(K (1 \le K \le N \times M)\) - количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа \(x_i\) и \(y_i\), означающие, что i-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце \((1 \le x_i \le N, 1\le y_i \le M)\). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

Если существует несколько путей минимальной длины, выведите любой. Если до сокровища невозможно добраться, в единственной строке выведите -1.

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	4 1 1 2 1 2 2 3 2 3 3
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.

Входные данные

В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= M, N <= 100.

Выходные данные

Вывести одно число.
 

Примеры

№	Входные данные	Выходные данные
1	5 10 ##..#####. .#.#.#.... ###..##.#. ..##.....# .###.#####	5

Жизнь завода по производству олимпиадных задач монотонна и однообразна: каждый день происходит одно и то же, вечера похожи как две снежинки и каждое утро всё начинается сначала - ничего не меняется на заводе по производству олимпиадных задач.
В частности, давно известно, когда в течение дня пара сотрудников встречается между собой.
При встрече сотрудники делятся друг с другом новостями.
Утром перед работой сотрудник номер 1 узнал нежелательную новость. Конечно же, он делится с ней при встрече со всеми остальными сотрудниками и они тоже узнают новость и начинаются делиться ей с другими. Если встречаются два сотрудника и один из них знает новость, то начиная с этого момента второй из них также знает новость. Ни один сотрудник не может встречаться с двумя или более сотрудниками одновременно (из соображений секретности). Пара сотрудников может встречаться несколько раз в течение дня.
Вы можете помешать ровно одной встрече за весь день. Выберите такую встречу, отмена которой приведёт к тому, что как можно меньше сотрудников завода узнают новость.

Входные данные
В первой строке входного файла задано два целых числа N (2 ≤ N ≤ 1000) и D (1 ≤ D ≤ 100000) — количество сотрудников и встреч соответственно. В следующих D строках заданы описания встреч. Каждое описание встречи состоит из трех
чисел A_i, B_i и T_i (1 ≤ A_i, B_i ≤ N, 1 ≤ T_i ≤ 10⁹) — пара номеров сотрудников и время встречи.

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

Примеры

№	Входные данные	Выходные данные
1	4 5 2 3 1 1 2 4 4 2 110 2 3 5 3 4 4	1 2 4

Давилон - самый крупный город на Луне. На Давилоне есть собственная система метро, состоящая из N станций и M железнодорожных линий. Станции пронумерованы от 1 до N. Каждой линией управляет компания. У каждой компании есть идентификационный номер. I-я (1<=i<=M) линия соединяет станцию pi и qi двунаправленно. Промежуточной станции нет. Этой линией управляет компания ci . Можно делать пересадки на станции, где доступно несколько линий. Система оплаты проезда, используемая в этой системе метро, немного странная. Когда пассажир использует только те линии, которые обслуживаются одной и той же компанией, тариф составляет 1 сантик (валюта Давилона). Каждый раз, когда пассажир переходит на линию, которой управляет компания, отличная от текущей линии, с пассажира взимается дополнительная плата за проезд в размере 1 сантик. В случае, если пассажир, перешедший с линии компании А на линию другой компании, снова переходит на линию компании А, дополнительный тариф взимается снова. Незнайка сейчас на станции 1 и хочет добраться до станции N на метро. Найдите минимально необходимый тариф.

Входные данные
В первой строке задается два целых числа N (2<=N<=10⁵) и M (0<=M<=2*10⁵). В каждой из следующих M строк записаны по 3 числа: pi, qi и ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=10⁶, pi ≠ qi. 

Выходные данные
Выведите минимальный требуемый тариф. Если добраться до станции N на метро невозможно, выведите -1.

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 1 2 1 2 3 1 3 1 2	1	Используйте линии компании 1: 1 → 2 → 3. Стоимость проезда 1 сантик.
2	8 11 1 3 1 1 4 2 2 3 1 2 5 1 3 4 3 3 6 3 3 7 3 4 8 4 5 6 1 6 7 5 7 8 5	2	Сначала используйте линии компании 1: 1 → 3 → 2 → 5 → 6. Затем используйте линии компании 5: 6 → 7 → 8. Стоимость проезда 2 сантика.
3	2 0	-1

 

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

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

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

Входные данные
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны.

Выходные данные
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений.

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 2 3 3 4 1 4 4 1	No

Дан неориентированный связный взвешенный граф с N вершинами и M ребрами, который не содержит ни петель, ни двойных ребер. I-е (\(1<=i<=M\)) ребро соединяет вершину ai и вершину bi на расстоянии ci. Будем считать, что петля - это ребро, где \(a_i=b_i\) (\(1<=i<=M\)), а двойные ребра - это два ребра, где \((a_i,b_i)=(a_j,b_j) \) или \((a_i,b_i)=(b_j,a_j)\) (\(1<=i<j<=M\)). Связный граф - это граф, в котором есть путь между каждой парой разных вершин. Найдите количество ребер, которые не входят ни в один кратчайший путь между любой парой различных вершин.

Входные данные
В первой строке задаются два целых числа N и M (\(2<=N<=100\), \(N-1<=M<=min(N \cdot (N-1)/2,1000)\)). Далее идет M строк по три целых числа в каждой строке: ai, bi, ci (\(1<=a_i, b_i<=N\), \(1<=c_i<=1000\)). Данный граф не содержит петель и двойных ребер. Данный граф является связанным.

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 1 2 1 1 3 1 2 3 3	1	В данном графе кратчайшие пути между всеми парами различных вершин следующие: Кратчайший путь от вершины 1 к вершине 2: вершина 1 → вершина 2, длина пути равна 1. Кратчайший путь от вершины 1 к вершине 3: вершина 1 → вершина 3, длина пути равна 1. Кратчайший путь из вершины 2 в вершину 1: вершина 2 → вершина 1, длина пути равна 1. Кратчайший путь от вершины 2 к вершине 3: вершина 2 → вершина 1 → вершина 3, длина пути равна 2. Кратчайший путь от вершины 3 до вершины 1: вершина 3 → вершина 1, длина пути равна 1. Кратчайший путь от вершины 3 к вершине 2: вершина 3 → вершина 1 → вершина 2, длина пути равна 2. Таким образом, единственное ребро, которое не содержится ни в одном кратчайшем пути, - это ребро длины 3, соединяющее вершину 2 и вершину 3, поэтому на выходе должно быть 1.
2	3 2 1 2 1 2 3 1	0	Каждое ребро содержится в некотором кратчайшем пути между парой различных вершин.

 

– Это что за остановка – Бологое иль Поповка? – А с платформы говорят: – Это город Ленинград.
«Вот какой рассеянный», Самуил Маршак
Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.

Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на n вершинах и m ребрах. Сeй невероятный факт, однако, нисколько не удивил Алину. Она давно мечтала побывать в одном таком городе — Петербурге. Его уникальной отличительной особенностью является то, что хотя бы половина его ребер — мосты (определение дано в конце условия). Так как никакие другие города Алине не интересны, она решила ограничиться расспросом находящихся на платформе эрудированных путешественников. Любой из их них может по данной вершине v сообщить любое ещё не названное ребро, исходящее из нее, или же заявить об отсутствии таковых.

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

Обратите внимание, что в графе могут присутствовать петли и кратные ребра.

Протокол взаимодействия
В первой строке стандартного потока ввода даны два целых числа n и m (1 ≤ n, m ≤ 100000 ) — число вершин и ребер в графе соответственно.

Для того, чтобы узнать очередное ребро, исходящее из u-й вершины (1 ≤ u ≤ n), нужно вывести « ? u  ». После этого ваша программа на вход получит целое число v (−2 ≤ v ≤ −1 или 1 ≤ v ≤ n)  — v=a+b−u, если существует ребро ab, которое инцидентно вершине u и ещё не было названо , −1, если такого ребра не существует и −2, если вы превысили допустимое число запросов. В последнем случае ваша программа должна немедленно завершиться, в ином случае жюри не гарантирует корректность полученного вами вердикта.

Вам разрешается задать не более 3n вопросов.

Чтобы сообщить, что ответ найден, требуется вывести « ! Yes » или « ! No », в зависимости от того, является ли загаданный граф Петербургом. В случае положительного ответа выведите \( {m \over 2}\) строк, по два целых числа u_i и v_i в каждой (1 ≤ u_i, v_i ≤ n), обозначающих, что ребро (u_i, v_i) является мостом. Любое ребро в приведенном списке должно встречаться не более одного раза (кратные ребра считаются различными).

Запрос на вывод ответа не входит в ограничение на 3n запросов.

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

Ввод-вывод в примерах демонстрирует пример взаимодействия вашей программы с проверяющей системой.

В первом примере был загадан граф на трех вершинах с ребрами (1, 2) , (2, 3)  и (3, 1) .

Во втором примере была загадан граф на четырех вершинах с ребрами (1, 2) , (2, 3) , (3, 4)  и (2, 3) .

Ребро, соединяющее вершины u и v, называется мостом, если после его удаления между вершинами u и v не существует пути.

Примеры

№	Входные данные	Выходные данные
1	3 3 2 2 -1 3 -1 -1	? 3 ? 1 ? 2 ? 1 ? 1 ? 3 ! No
2	4 4 2 3 2 -1 4 -1 -1 -1	? 1 ? 2 ? 3 ? 1 ? 3 ? 3 ? 2 ? 4 ! Yes 1 2 3 4

В тридесятом государстве есть N деревень. Некоторые пары деревень соединены дорогами. В целях экономии, “лишних” дорог нет, т.е. из любой деревни в любую можно добраться по дорогам единственным образом.
Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение. А именно, он хочет узнать, какое минимальное число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из P деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа изолирована от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы).
Вы должны написать программу, помогающую ему в этом.

Формат входных данных
Первая строка входного файла содержит два числа: N и P (1 ≤ P ≤ N ≤ 150). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 1 до N), которые эта дорога соединяет. Все числа во входном файле разделены пробелами и/или переводами строки.

Формат выходных данных
В выходной файл выведите единственное число — искомое количество дорог.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 2 1 2 3 2	1
2	11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11	2	группа деревень (1, 2, 3, 6, 7, 8) окажется изолированной от остальных, если разрушить дороги 1–4 и 1–5.

Беси любит искать пути в лабиринтах и играть в "крестики-нолики". Фермер Джон придумал для неё способ играть в обе игры одновременно!
Первое - "крестики-нолики" - вместо размещения X и O на решётке 3×3, коровы играют с М и О на решётке 3×3. Во время хода корова может поставить М или О в любую пустую ячейку (в отличие от стандартной игры, где один игрок всегда ставит X, а другой всегда О). Победитель этой игры тот, кто первый получит слово 'MOO' горизонтально, вертикально или по диагонали. В обратном порядке тоже засчитывается, то есть 'OOM' тоже выигрышная комбинация. Как и в стандартной игре, возможно заполнить всё поле и никто не выиграл. Ход в игре указывается 3 символами 'Mij' или 'Oij', где i и j в интервале 1…3 и указывают строку и столбец, в которые ставится соответствующий символ 'M' или 'O'.

Фермер Джон спроектировал для Беси квадратный лабиринт, представляющий решётку из N×N ячеек (3≤N≤25). Некоторые ячейки, включая все граничные ячейки, содержат большие стоги сена, предотвращающие Беси от захода в эти ячейки. Беси может свободно двигаться во все другие ячейки лабиринта предпринимая шаги в в обычных направлениях -север, юг, запад, восток. Некоторые ячейки содержат листок бумаги, на котором написан ход для "крестиков ноликов". По ходу тго, как Беси двигается по лабиринту, каждый раз, когда она попадает на такую ячейку, она должна сделать соответствующий ход в игре "крестики-нолики", в которую она играет параллельно с движением по лабиринту. Если соответствующая ячейка в "крестиках-ноликах" уже занята, то она не предпринимает никаких действий. У неё нет противника в игре "крестики-нолики", но некоторые из ячеек лабиринта могут противоречить её цели составить слово 'MOO'.

Если Беси останавливает игру "крестики-нолики" сразу после победы, определите количество различных выигрышных конфигураций в "крестиках-ноликах", которые она может сгенерировать, двигаясь соответственно в лабиринте.

ФОРМАТ ВВОДА
Первая строка содержит N.
Лабиринт определяется следующими N строками, каждая из которых содержит 3N символов. Каждая ячейка описывается блоком из 3 символов: '###' для стены, '...' для пустой ячейки, 'BBB' для ячейки в которой стартует Беси, ход для "крестиков-ноликов". Ровно одна ячейка содержит 'BBB'.

ФОРМАТ ВЫВОДА 
Выведите количество различных выигрышных комбинаций для "крестиков-ноликов" (возможно 0), которые Беси может сгенерировать движением по лабиринту, остановившись после победы.

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 ##################### ###O11###...###M13### ###......O22......### ###...######M22###### ###BBB###M31###M11### ###...O32...M33O31### #####################	8	В этом примере имеется 8 выигрышных комбинаций, которые Беси может достичь: O.M .O. MOM O.. .O. .OM O.M .O. .OM O.. .O. MOM O.. ... OOM ..M .O. OOM ... .O. OOM ... ... OOM Пояснения к одной из них: O.. ... OOM Здесь Беси сначала посещает ячейку O11, затем двигается в нижний коридор, посещая O32, M33, O31. Игра прекращается, поскольку Беси выиграла.

 

Предприятие «Авто-2010» выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.

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

Входные данные
Первая строка входного файла содержит число n (1≤ n ≤ 100000) — количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂, p_n, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 10⁹ секунд.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-я строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера. В i-й строке нет повторяющихся номеров деталей. Сумма всех чисел k_i не превосходит 200000.

Известно, что не существует циклических зависимостей в производстве деталей.

Выходные данные
В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.
 

Ввод	Вывод
3 100 200 300 1 2 0 2 2 1	300 2 2 1
2 2 3 1 2 0	5 2 2 1
4 2 3 4 5 2 3 2 1 3 0 2 1 3	9 3 3 2 1