Задача 0A. Hello, world! ≡

Условие

Требуется написать программу, которая печатает "Hello, world!" (без кавычек)

Задача 0B. Олины торты ≡

Условие

Сегодня к Оле в гости придет N одногруппников, из-за чего она решила приготовить N тортов. В ее распоряжении есть M грамм сахара. Поскольку Оля не хочет никого обидеть, в каждом торте должно быть одинаковое количество сахара. Какое максимальное количество сахара может содержать каждый торт?

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

Входные данные содержат числа M и N, каждое на новой строке.

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

Необходимо вывести единственное число — максимальное количество сахара.

Ограничения

1 < N, M < 10000

Примеры тестов

10
2

5

6
4

1.5

Задача 0C. Заплыв ≡

Условие

Оксана любит плавать и готовится к заплыву через Амурский залив. Для подготовки она каждый день приходит в бассейн и проводит там несколько часов, переплывая от одного края бассейна до другого. Длина бассейна, где занимается Оксана — N метров. Она успевает пересечь его за M секунд, и ещё K секунд тратит на разворот. Сколько метров Оксана успеет проплыть за L минут?

Формат входного файла

Первая строка входного файла содержит четыре натуральных числа: N M K L.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество проплытых метров.

Ограничения

1 ≤ N, M, K, L ≤ 1000

Примеры тестов

25 76 2 45

865

50 50 1 60

3530

Задача 0D. Максимальный элемент массива ≡

Условие

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

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

В первой строке записано одно целое число N — количество элементов в массиве.

Далее следует N целых чисел a_i — элементы массива.

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

Выведите единственное целое число — наибольший элемент массива.

Ограничения

1 ≤ N ≤ 10³

 − 10⁶ ≤ a_i ≤ 10⁶

Описание подзадач и системы оценивания

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

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

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

Подсказка

Для того чтобы считывать элементы массива на языке Pascal следует использовать функцию read(). Применение функции readln() невозможно, так как все элементы массива записаны в одной строке.

Примеры тестов

3
1 3 2

3

5
8 5 6 10 3

10

1
1000000

1000000

Задача 0E. Подсчёт баллов за задачу ≡

Условие

В одной из задач итоговой олимпиады летней школы по информатике имеется N тестов. i-ый тест оценивается в a_i баллов. Итоговый балл за задачу — сумма баллов за каждый тест, ответ на который является правильным.

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

Формат входного файла

В первой строке файла содержится единственное число N.

Во второй строке файла содержатся N чисел — на i-ом месте находятся баллы за i-ый тест.

В третьей строке файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 100

Примеры тестов

5
1 2 3 5 10 
+-++-

9

6
1 1 3 5 10 25
+-+--+

29

Задача 0F. Стремление к нулю ≡

Условие

Дано число N и массив из S целых чисел A_i.

За одну операцию можно заменять число N на любое из чисел N + A_i, N − A_i, N × A_i, N / A_i.

Второй операнд может быть любым элементом массива A.

Деление выполняется нацело, с округлением вниз.

Необходимо рассчитать минимальное количество операций, необходимых, чтобы получить из числа N число 0.

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

Первая строка входных данных содержит целое число N.

Вторая — целое число S.

Третья — S целых чисел, массив A.

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

Выходные данные должны содержать одно целое число — минимальное количество операций.

Ограничения

0 ≤ N, A_i ≤ 2 * 10⁹

1 ≤ S ≤ 100

Пояснения к примеру

100 / 25 = 4 ; 4 - 4 = 0

100 / 11 = 9 ; 9 / 11 = 0

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

Примеры тестов

100
6
4 7 10 5 25 11

2

Задача 0G. Уравнение для 5 класса ≡

Условие

Уравнение для пятиклассников представляет собой строку длиной 5 символов. Второй символ строки является либо знаком '+' (плюс) либо '-' (минус), четвёртый символ — знак '=' (равно). Из первого, третьего и пятого символов ровно два являются цифрами из диапазона от 0 до 9, и один — буквой x, обозначающей неизвестное.

Требуется решить данное уравнение относительно x.

Формат входного файла

Формат выходного файла

Примеры тестов

x+5=7

2

3-x=9

-6

Задача 0H. Среднее арифметическое ≡

Условие

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

Формат входного файла

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

Формат выходного файла

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

Ограничения

1 < n < 10⁵

Примеры тестов

3
1 3 5

3

Задача 1A. Неоплаченные счета ≡

Условие

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

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

Необходимо определить, сколько минут потребуется Василию Ивановичу на оплату всех счетов.

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

Входные данные содержат два целых числа N и M. Каждое число записано в новой строке.

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

Выведите одно число - минимальное время, за которое Василий Иванович оплатит все счета.

Ограничения

1 ≤ N, M ≤ 10⁹

Примеры тестов

10
5

11

10
3

16

Задача 1B. Стажeры ≡

Условие

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

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

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

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

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

В первой строке входных данных содержится целое положительное число N ≤ 1000. Далее в N строках содержатся названия вузов, в которых учились стажeры. Названия вузов - непустые строки, состоящие не более, чем из десяти заглавных латинских букв.

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

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

Если составить такую рассадку невозможно программа должна вывести строку «IMPOSSIBLE». Строки названия вузов необходимо выводить через пробел.

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

Примеры тестов

4
HSE
HSE
MIPT
MSU

HSE MSU HSE MIPT 

4
HSE
HSE
MSU
HSE

IMPOSSIBLE

Задача 1C. Переезд ≡

Условие

В связи с переездом в новый офис компании необходимо распределить опенспейсы между отделами. Известно, что в компании N отделов, в i-ом отделе A_i cотрудников. Теперь перед генеральным директором стоит задача: выделить каждому отделу собственный опенспейс. В новом офисе есть M ≤ N опенспейсов, в j-ом опенспейсе есть B_j рабочих мест. Для работы отдела необходимо, чтобы у каждого сотрудника было своe рабочее место, и ещe одно место нужно для начальника отдела. К сожалению, ремонт опенспейсов завершeн и изменить расстановку рабочих мест невозможно. Помогите генеральному директору распределить отделы компании по опенспейсам.

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

Для справки. Оpen space в переводе с английского - офис открытого типа, то есть помещение спланировано таким образом, что создается единое рабочее пространство для сотрудников.

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

На первой строке входного файла расположены числа N и M (1 ≤ N ≤ M ≤ 1000). На второй строке расположено N чисел - A₁, . . . , A_N (1 ≤ A_i ≤ 1000 для всех 1 ≤ i ≤ N). На третьей строке расположено M чисел B₁, ..., B_M (1 ≤ B_j ≤ 1000 для всех 1 ≤ j ≤ M).

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

Выведите на первой строке число P - количество отделов, которые удастся распределить по опенспейсам. На второй строке выведите распределение отделов по опенспейсам - N чисел, i-е число должно соответствовать номеру опенспейста, в котором разместится i-ый отдел (нумерация отделов и опенспейсов начинается с 1).

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

Примеры тестов

3 3
1 2 3
2 3 4

3
1 2 3

Задача 1D. Печать документа ≡

Условие

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

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

На вход программы сначала поступает число N , количество листов в итоговом отчeте (1 ≤ N ≤ 10⁹), затем - число M (1 ≤ M ≤ 15) и далее M попарно различных чисел X₁, X₂, ..., X_M (1 ≤ X_I ≤ 10⁹).

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

Сначала выведите K - количество пачек, которое придется передать со склада канцелярских товаров, если суммарно в этих пачках будет N листов бумаги. Далее выведите K чисел, задающих количество листов в каждой из пачек, которые требуется передать в отдел. Если решений несколько, выведите вариант, в котором придeтся передать минимальное количество пачек. Если таких вариантов несколько, выведите любой из них.

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

Примеры тестов

108 7
45 35 12 4 3 1 931751396

5
45 35 12 12 4

7 2
1 2

-1

5 2
3 4

0

Задача 1E. Суперсекретная информация ≡

Условие

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

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

Необходимо написать программу, которая выведет минимальное время, которое потребуется сотруднику для того, чтобы добраться из офиса a в офис b.

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

Сначала вводится число N - общее число офисов компании (1 ≤ N ≤ 100), затем в новой строке - номера офисов a и b (1 ≤ a, b ≤ N). Далее следует число рейсов корпоративных шаттлов R (0 ≤ R ≤ 10⁵). После идут описания рейсов шаттлов: каждый рейс задается номером офиса отправления, временем отправления, номером офиса назначения и временем прибытия (все времена - целые от 0 до 10000). Если в момент t сотрудник приезжает в какой-то офис, то уехать из него он может в любой момент времени, начиная с t.

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

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

Примеры тестов

3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10

5

Задача 4D. Извлечение ключа ≡

Условие

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

Строка s₂ является подпоследовательностью строки s₁, если еe можно получить путeм удаления некоторых символов из s₁, не меняя порядок оставшихся символов.

Например если s₁ это abracadabra, то еe подпоследовательностями являются babr, arcada, aacaa и r. В то же время, такие строки как bob, bard и d_c не являются подпоследовательностями строки s₁.

Ключ, который хочет передать Алиса, состоит из малых букв латиницы и обладает следующим свойством: любые два рядом стоящие в нeм символа находятся рядом и в алфавите. То есть следующий символ ключа по отношению к предыдущему является либо следующей, либо предыдущей буквой латиницы. Назовeм такие строки «правильными». Например, правильными являются строки cdef edef gh или abababab, а вот строки abba или cede не являются правильными.

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

Пояснения к примеру

В присланной Алисой строке bdaedbceab содержатся следующие правильные подпоследовательности длины 5: babab, babcb и dedcb. Последняя, так как она лексикографически самая большая, и будет ответом.

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

В первой строке содержится число n - длина строки, которую прислала Алиса.

1 ≤ n ≤ 3·10⁵.

Во второй строке приведена сама строка, которую прислала Алиса. Она состоит из малых букв латиницы.

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

В ответ вывести одну строку - «спрятанный» в исходной строке по указанным выше правилам ключ.

Примеры тестов

10
bdaedbceab

dedcb

Задача 5B. Космические связи ≡

Условие

Ученые решили изучить состояние межпланетных отношений. В первую очередь им нужно посчитать количество планетарных коалиций (групп планет). Они имеют информацию об n планетах во Вселенной. У каждой планеты есть координаты в двухмерном пространстве x и y. Планета состоит в некоторой коалиции, если она попадает в радиус r хотя бы одной планеты из этой коалиции. Они просят Вас написать программу, которая определит количество коалиций во Вселенной.

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

В первой строке записано два целых числа n (1 ≤ n ≤ 10³) и r (1 ≤ r ≤ 10⁶) — количество планет, которые известны ученым, и радиус взаимодействия планет.

В следующих n строках записано по два числа x и y ( − 10⁶ ≤ x, y ≤ 10⁶) — координаты планет.

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

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

Методика проверки Программа проверяется на 50 тестах. Прохождение каждого теста оценивается в 2 балла. Тест из примера к задаче при проверке не используется.

Примеры тестов

5 3
1 1
3 4
6 3
5 1
4 4

2

Задача 6A. Сплав ≡

Условие

Сплав состоит из n компонентов. Для каждого компонента i известна его процентная доля массы в сплаве r_i . В лаборатории имеются все компоненты сплава, однако, можно использовать не более m_i килограмм вещества i-того компонента. Напишите программу, которая определит максимальную возможную массу сплава, которую можно получить.

Пояснения к примеру

В приведенном примере масса сплава равна 27,5 кг. Взяв 50, 40 и 10% от этой массы, получим 13,75, 11 и 2,75 кг соответственно. Массы соответствующих компонентов не превосходит этих значений. Но при этом изготовить сплав большей массы не получится, поскольку не хватит вещества второго компонента.

Программа проверяется на 20 тестах. Прохождение каждого теста оценивается в 0,5 балла. Тест из условия задачи при проверке не используется.

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

На вход программы в первой строке подается одно натуральное число n — количество компонентов в сплаве. 1 ≤ n ≤ 30. Во второй строке через пробел записаны n целых неотрицательных чисел r₁... r_n — процентные доли компонентов в сплаве.

0 ≤ r_i ≤ 100. Гарантируется, что сумма всех r_i равна 100. Если r_i = 0, то это означает, что компонент i в сплаве не используется. В третьей строке через пробел записаны n натуральных чисел m₁... m_n — масса вещества каждого компонента. 0 < m_i < 1000.

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

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

Ответ будет считаться верным, если выведенное число отличается от правильного ответа не более чем на 0, 001.

Примеры тестов

1
100
17

17.0

Задача 6B. Съемка заповедника ≡

Условие

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

Каждый снимок имеет вид прямоугольника с шириной a и высотой b. Стороны прямоугольника должны быть параллельны осям координат. Поворачивать снимки нельзя. Снимки могут выходить за границу заповедника или накладываться друг на друга. При заказе каждого снимка можно указать его местоположение. Администрация заповедника хочет заказать как можно меньше снимков.

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

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

На вход программы в первой строке через пробел подаются три натуральных числа n, a, b — ширина криволинейной трапеции (количество столбиков из которых состоит трапеция), а также ширина снимка и высота снимка. 1 ≤ n ≤ 2000; 1 ≤ a ≤ 2000; 1 ≤ b ≤ 5000. Во второй строке через пробел записаны n целых неотрицательных чисел h₁... h_n — высоты столбиков. 0 ≤ h_i ≤ 5000.

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

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

Методика проверки и пояснение к тесту Рисунки в условии задачи соответствуют тесту. Как видно из рисунков, минимальное количество снимков равно девяти.

Программа проверяется на 15 тестах. Прохождение каждого теста оценивается в 1 балл. Тест из условия задачи при проверке не используется.

Примеры тестов

23 5 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1

4

Задача 7A. Конвертер графов ≡

Условие

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

Формат входного файла

Первая строка входного файла содержит два слова. Первое — название формата графа во входном файле. Второе — название формата, в котором граф необходимо вывести.

Начиная со второй строки в файле содержится описание графа в одном из следующих форматов

• edges — список ребер. В этом случае первая строка описания графа должна содержать два целых числа N, M — количество вершин и количество ребер соответственно. Далее каждая следующая строка содержит два числа u и v — начало и конец очередного ребра.
• lists — списки смежности. В этом случае первая строка описания графа должна содержать целое число N — количество вершин графа. Далее i-я строка (начиная со второй) содержит описание списка смежности (i − 1)-й вершины. Первое целое число в строке c_i — количество вершин, в которые выходят ребра из (i − 1)-й вершины. Далее через пробел следует c_i целых чисел — номера вершин, в которые выходят ребра из (i − 1)-й.
• mat — матрица смежности. В этом случае первая строка описания графа должна содержать целое число N — количество вершин графа. Далее следует N строк по N чисел 0 или 1 — описание матрицы смежности. Если в i-й строке на j-й позиции находится единичка, значит в графе есть ребро из (i − 1)-й вершины в j-ю.

Формат выходного файла

Выходной файл должен содержать описание графа в требуемом формате.

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ N²

Примеры тестов

edges mat
3 4
1 2
2 3
1 3
2 2

3
0 1 1
0 1 1
0 0 0

mat lists
4
1 0 1 1
0 0 0 0
1 1 0 0
0 1 1 0

4
3 1 3 4
0
2 1 2
2 2 3

Задача 7B. Интернет по ЛЭП ≡

Условие

Один из интернет-провайдеров решил опробовать новую технологию — передачу данных по линиям электропередач. Для этого на подстанциях были установлены N ретрансляторов.

Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору. Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод, назовем нагрузкой на данный провод для i-го ретранслятора. Максимум из нагрузок на все провода для i-го ретранслятора называется нагрузкой на данный ретранслятор. Известно, что по проводам электросети сигнал может пройти от одного ретранслятора к другому единственным образом.

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
1 2
2 3

2 1 2

4
1 2
1 3
1 4

1 3 3 3

Задача 7C. Бег по коридору ≡

Условие

Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и N пикселей по горизонтали. Каждый пиксель определяется координатами (a, b), где a — номер строки от 1 до 2, а b — номер столбца от 1 до N.

На дисплее с таким разрешением уже можно играть и Петя разрабатывает одну из игр — "Бег по коридору". По правилам игры, каждый пиксель может быть либо свободен, либо занят препятствием, либо занят игроком, либо занят эликсиром. Игрок может перемещаться в один из смежных пикселей, не занятых препятствием (смежными называются пиксели, соседствующие либо в строке, либо в столбце).

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

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

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

Формат входного файла

В первой строке входного файла содержится число N — горизонтальное разрешение дисплея. Далее следует описание игрового поля — пара строк длиной N каждая. Символ "." (точка) соответствует свободному пикселю, символ "#" (решетка) — занятому препятствием, символ "X" (прописная латинская X) — пикселю с эликсиром.

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

Гарантируется, что можно добраться до N-ого столбца.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 100

Примеры тестов

2
..
.#

1

6
....X.
#XXX..

3

Problem 7D. SST for sparse graph ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 10
2 3 10
3 1 10

20

Задача 7E. Бюрократия ≡

Условие

В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата. Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник. Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого. Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы гарантировала, что никто из них ему не откажет.

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

4 3
1 2
1 3
3 4

1 3 2 4