Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Обход в глубину

Условие задачи  
ID 33313
Цепочка слов
Темы: Обход в глубину    Бор   

Цепочкой слов длины n назовем последовательность слов w1, w2, ..., wn такую, что для 1 ≤ i ≤ n слово wi является собственным префиксом слова wi + 1.
 
Напомним, что слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u.
 
Задано множество слов S = {s1, s2, ..., sm}. Найдите максимальную длину цепочки слов, которую можно построить, используя (возможно, не все) слова этого множества.
 
Входные данные
Первая строка входного файла содержит целое число m(1 ≤ m ≤ 255). Каждая из последующих m строк содержит по одному слову из множества S.
 
Все слова не пусты, имеют длину, не превосходящую 255 символов, и состоят только из строчных букв латинского алфавита.
 
Выходные данные
В выходной файл выведите ответ на задачу.

Ввод Вывод
3
a
ab
abc
 
5
a
ab
bc
bcd
add
2

ID 33314
Type Printer
Темы: Бор    Обход в глубину   

Вам нужно напечатать N слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:
 
Добавить букву в конец слова, находящегося сейчас на принтере.
Удалить последнюю букву из слова, находящегося сейчас на принтере. Эту операцию можно делать, только если слово содержит хотя бы одну букву.
Напечатать слово, находящееся на принтере (при этом слово никуда не исчезает, можно печатать его ещё раз и ещё раз).
Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.
 
Каждая из трёх операций занимает одну единицу времени. Вам нужно найти последовательность операций, которая печатает данные N слов за минимальное время. Если минимальных последовательностaей несколько, выведите любую.
 
Входные данные
Ваша программа должна считать следующие входные данные:
 
На первой строке число N (1<=N<=25000).
На следующих N строках слова, состоящие из маленьких букв латинского алфавита. Длина каждого слова не превышает 20. Все слова различны.
 
Выходные данные
Ваша программа должна вывести следующие данные:
 
На первой строке M — число операций.
На следующих M строках по одному символу — описание операций. Каждая операция описывается одним символом:
Добавление символа обозначается собственно символом.
Удаление символа обозначается символом «-» (минус, ASCII-код 45).
Операция «напечатать текущее слово» обозначается символом «P» (заглавная латинская буква P).

Ввод Вывод
3
print
the
poem
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P

ID 24753
Топологическая сортировка
Темы: Обход в глубину   

Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.

Входные данные: В первой строке содержатся два натуральных числа n и m (1≤n≤105, 1≤m≤105) — количество вершин и рёбер в графе соответственно. Далее в m строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

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

Примеры
Входные данные Выходные данные
1 4 4
1 4
4 3
4 2
3 2
1 4 3 2

ID 33465
Обход графа. Компонента связности
Темы: Обход в глубину   

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

Входные данные: В первой строке входных данных содержатся два числа: N и S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), где N – количество вершин графа, а S – заданная вершина. В следующих N строках записано по N чисел – матрица смежности графа, в которой 0 означает отсутствие ребра между вершинами, а 1 – его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные: Выведите одно целое число – искомое количество вершин.

Примеры

Входные данные Выходные данные
1 3 1
0 1 1
1 0 0
1 0 0
3

ID 22021
Компоненты связности
Темы: Обход в глубину   

В неориентированном графе посчитать количество компонент связности. В графе могут быть петли и кратные ребра.
 
Входные данные: В первой строке записаны сначала два числа N и M, задающие соответственно количество вершин и количество ребер (1<=N<=100, 0<=M<=10000), а затем перечисляются ребра. Каждое ребро задается двумя номерами вершин, которые оно соединяет
 
Выходные данные: Выведите одно число - количество компонент связности
 
Примеры
Входные данные Выходные данные
1
3 4
1 1
1 2
1 3
2 3
1
2
5 3
1 1
1 2
2 1
4
3 5 0 5

ID 33146
Баобаб
Темы: Обход в глубину   

Дан неориентированный невзвешенный граф. Необходимо определить, является ли он деревом.
 
Входные данные: В первой строке содержится одно натуральное число N (N ≤ 100) - количество вершин в графе. Далее в N строках по N чисел - матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.
 
Выходные данные: Вывести "YES", если граф является деревом, и "NO" иначе.

Примеры
Входные данные Выходные данные
1
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
NO
2
3
0 1 0
1 0 1
0 1 0
YES

ID 33147
Банкет
Темы: Обход в глубину   

На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.
 
Входные данные: В первой строке входных данных содержатся два числа: N и M (1 <= N,M <= 100), где N – количество ОВП, а M – количество пар ОВП, которые не могут сидеть за одним столом. В следующих M строках записано по 2 числа – пары ОВП, которые не могут сидеть за одним столом.
 
Выходные данные: Если способ рассадить ОВП существует, то  выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.

Примеры
Входные данные Выходные данные
1
3 2
1 2
1 3
YES
1

ID 18701
Поиск циклов в графе
Темы: Обход в глубину   

Дан ориентированный невзвешенный связный граф. Требуется определить, содержит ли он циклы.
 
Входные данные: Первая строка содержит одно натуральное число n — количество вершин (0 ≤ n ≤ 1 111).
Следующие n строк содержат матрицу смежности графа. Если в позиции (i, j) квадратной матрицы стоит единичка, то i-ый и j-ый ребра соединены ребрами, а если нолик, то не соединены. При этом ребро направленно из i-ого в j-ое ребро графа, и j-ое и i-ое ребро не соеденены ребрами.
 
Выходные данные: Первая строка должна содержать YES, если граф содержит цикл и NO — в противном случае.

Примеры
Входные данные Выходные данные
1
8
0 1 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
YES

 

ID 27034
Рекурсивный DFS
Темы: Обход в глубину   

Дана матрица N (1 <= N <= 100) на M (1 <= M <= 100). В матрице имеются ‘.’ – пустые клетки и ‘#’ – клетки, которые нельзя посетить. Ходить можно только вверх, вниз, влево и вправо. Дано q запросов: номер строки и номер столбца, если эта клетка – ‘#’, то она станет ‘.’, иначе – ‘#’. Для каждого из q запросов определить, достижима ли из клетки Sx;Sy клетка tx;ty. Вывести на каждой строчке “Yes”, если достижима, и “No” - иначе. Гарантируется, что клетка Sx; Sy и клетка tx; ty не являются ‘#’ клеткой в каждом запросе.
Входные данные.
На первой строчке вводятся числа Sx (1 <= Sx <= 100), Sy (1 <= Sy <= 100), tx (1 <= tx <= 100), ty (1 <= ty <= 100), N (1 <= N <= 100), M(1 <= M <= 100) и q (1 <= q <= 100). На следующих N строках дается матрица, где ‘.’ – пустая клетка и ‘#’ – клетка, которую нельзя посетить. На следующих q строках дан номер строки и номер столбца, которые надо изменить.
 
Выходные данные.
Вывести на каждый из q запросов “Yes”, если из клетки Sx; Sy в клетку tx; ty можно попасть, “No” – иначе.
 
Ввод Вывод
1 1 2 3 3 3 2
.##
##.
###
1 2
2 2
No
Yes
 
Пояснение:
После первого запроса матрица будет такой:
.  .  #
# # .
# # #
Из точки 1;1 в 2;3 нет прохода, следовательно, выводим “No”.

После второго запроса матрица будет такой:
.  .  #
# .  .
# # #
Из точки 1;1 в 2;3 есть проход, следовательно, выводим “Yes”. Выделен путь, по которому мы сможем идти.

(с) Всеволод Шалдин
 

ID 33513
Грядки*
Темы: Обход в глубину   

Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

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

Входные данные
В первой строке находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. 1 ≤ N, M ≤ 200.

Выходные данные
Вывести одно число - количество грядок на садовом участке.
Примеры

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

ID 34975
*Производство деталей
Темы: Обход в глубину   

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

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

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

Входные данные
Первая строка входного файла содержит число n (1≤ n ≤ 100000) — количество деталей двигателя. Вторая строка содержит n натуральных чисел p1, p2, pn, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 109 секунд.

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

ID 27212
Есть ли цикл?
Темы: Обход в глубину    Алгоритм Флойда   

Дан ориентированный граф. Требуется определить, есть ли в нем цикл.
 
Входные данные
В первой строке вводится число вершин N≤ 50. Далее в N строках следуют по N чисел, каждое из которых – 0 или 1. j-ое число в i-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из i-ой вершины в j-ую. Гарантируется, что на диагонали матрицы будут стоять нули.
 
Выходные данные
Выведите 0, если в заданном графе цикла нет, и 1, если он есть.

Примеры
Входные данные Выходные данные
1
3
0 1 0
0 0 1
0 0 0
0
2
3
0 1 0
0 0 1
1 0 0
1

ID 38130
Лабиринт Tac Toe
Темы: Применение обхода в глубину    Обход в глубину   

Беси любит искать пути в лабиринтах и играть в "крестики-нолики". Фермер Джон придумал для неё способ играть в обе игры одновременно!
Первое - "крестики-нолики" - вместо размещения 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. Игра прекращается, поскольку Беси выиграла.

 

ID 38303
Выбор гурмана
Темы: Динамическое программирование на графах    Обход в глубину    Система непересекающихся множеств   

Гурман Яблочков работает редактором известного гастрономического издания. Он разъезжает по всему миру, дегустируя новые изыски именитых шеф-поваров самых фешенебельных ресторанов высокой кухни. У Яблочкова есть свой фирменный способ ревью: в каждом заведении Яблочков заказывает два набора блюд в разные дни. Все заказанные блюда разные, так как Яблочков не любит есть одно и то же. Для каждой пары блюд из разных наборов он точно помнит, какое из них лучше по его ощущениям, или что они одинаковы по вкусовым качествам. Затем гурман оценивает каждое блюдо положительным целым числом.

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

Гурман в первый день дегустировал набор из n блюд, во второй день набор из m блюд. Он составил таблицу ощущений a размером nm, в которой описал свои впечатления. Если по мнению эксперта блюдо i из первого набора лучше блюда j из второго набора, то aij равно « > », в противоположном случае aij равно « < ». Блюда также могут быть равны по уровню, тогда aij равно « = ».

Теперь Яблочков хочет, чтобы вы помогли ему оценить каждое блюдо в наборах целым положительным числом. Так как Яблочков очень строгий дегустатор, то постарается оценить блюда так, чтобы максимальная из оценок была как можно меньше. В то же время Яблочков очень справедливый, поэтому никогда не оценивает блюда так, чтобы это шло вразрез с его ощущениями. Другими словами, если aij равно « < », то оценка блюда i из первого набора должна быть меньше оценки блюда j из второго набора, если aij равно « > », то должна быть больше, а если aij равно « = », то должна совпадать.

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

Входные данные
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 1000 ) — количества блюд в каждый из двух дней.

Каждая из следующих n строк содержит строку из m символов. j-й символ в i-й строке задаёт значение aij. Все строки состоят только из символов « < », « > » и « = ».

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

В случае, если сделать корректную оценку можно, во второй строке выведите n целых чисел — оценки блюд первого набора, а в третьей строке m целых чисел — оценки блюд второго набора.
 

Примеры
Входные данные Выходные данные Пояснения
1 3 4
>>>>
>>>>
>>>>
Yes
2 2 2 
1 1 1 1 
Все блюда первого дня лучше всех блюд второго дня. Значит, самой высокой оценкой будет 2 для всех блюд первого дня.
2 3 3
>>>
<<<
>>>
Yes
3 1 3 
2 2 2 
 
3 3 2
==
=<
==
No Таблица противоречива: нет ни одного набора оценок, который удовлетворял бы ей.

ID 38349
Введите одностороннее движение
Темы: Обход в глубину   

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

Входные данные
Во входном файле записано сначала число N — количество городов (1≤N≤1000). Затем записано число M — количество дорог (1≤M≤100000). Далее идет M пар чисел, задающих дороги (каждая дорога описывается номерами городов, которые она соединяет). Не бывает дорог из некоторого города в тот же город. Между двумя городами может быть несколько дорог. Гарантируется, что до введения одностороннего движения можно было попасть из любого города в любой другой.

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

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

Примеры
Входные данные Выходные данные
1 4
6
1 2
1 2
2 3
2 4
4 3
1 4
2 1
2 1
3 2
4 2
4 3
1 4

ID 38355
Перегоны
Темы: Обход в глубину   

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

Входные данные
Во входном файле записаны сначала числа N — количество станций (2 ≤ N ≤ 100) и E — количество пар станций, расстояния между которыми заданы (0 ≤ E ≤ 10000). Далее идет E троек чисел, первые два числа каждой тройки задают номера станций (это числа из диапазона от 1 до N), а третье — расстояние между этими станциями (все эти расстояния заданы точно и выражаются вещественными неотрицательными числами не более чем с 3-я знаками после десятичной точки).

Выходные данные
В случае, когда восстановить длины перегонов можно однозначно, в выходной файл выведите сначала число 1, а затем N–1 вещественное число. Первое из этих чисел должно соответствовать расстоянию от 1-й станции до 2-й, второе — от 2-й до 3-й, и так далее. Все числа должны быть выведены с точностью до 3-х знаков после десятичной точки.

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

Примеры
Входные данные Выходные данные
1 2 3
1 1 0
2 2 0
2 1 2.5
1
2.500
2 15 13
1 2 1
1 3 2
1 4 3
1 5 4
1 6 5
1 7 6
1 8 7
1 9 8
1 10 9
1 11 10
1 12 11
1 13 12
15 14 13
2

ID 38371
Кодовый замок
Темы: Обход в глубину   

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

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

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

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

В первой строке входного файла находятся три целых числа h, w и k (1 ≤ h, w ≤ 30; 1 ≤ k ≤ 10). Каждая из последующих h строк содержит w символов. Символ «#» обозначает кнопку, а «.» — ее отсутствие.

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

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

Примеры
Входные данные Выходные данные
1
2 2 2
.#
##
2
2
5 6 7
.#....
##.##.
..#.#.
.####.
.....#
3

ID 38444
Деревни
Темы: Динамическое программирование    Алгоритмы на графах    Обход в глубину    Динамическое программирование на графах   

В тридесятом государстве есть 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.

ID 38569
Построение
Темы: Обход в глубину   

Группа солдат-новобранцев прибыла в армейскую часть 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

ID 38638
Площадь комнаты
Темы: Обход в глубину    Рекурсия   

Требуется вычислить площадь комнаты в квадратном лабиринте.

Входные данные
В первой строке  вводится число N – размер лабиринта (3 <= N <= 10). В следующих N строках задан лабиринт (‘.’ – пустая клетка, ‘*’ – стенка). И наконец, последняя строка содержит  два числа – номер строки и столбца клетки, находящейся в комнате, площадь которой необходимо вычислить. Гарантируется, что эта клетка пустая и что лабиринт окружен стенками со всех сторон.

Выходные данные
Требуется вывести единственное число – количество пустых клеток в данной комнате.

Примеры
Входные данные Выходные данные
1
5
*****
**..*
*.*.*
*..**
*****
2 4
3