Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.

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

Дана последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	8

Двоичное дерево поиска Деревья

✓ 19✗ 45700средняяВойти и решать

Сбалансированность#44649

Дерево называется сбалансированным, если для любой его вершины высота левого и правого поддерева для этой вершины различаются не более чем на 1.

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. Постройте дерево, соответствующее данной последовательности.

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

Определите, является ли дерево сбалансированным, выведите слово YES или NO.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	YES

Двоичное дерево поиска Деревья

✓ 20✗ 33700средняяВойти и решать

Выведи развилки#44648

Для полученного дерева выведите список всех вершин, имеющих по два ребёнка, в порядке возрастания.

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. Постройте по этой последовательности дерево.

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

Выведите ответ задачи.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	3 5 7

Двоичное дерево поиска Деревья

✓ 18✗ 16700средняяВойти и решать

Выведи листья#44647

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

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	1 4 6 8

Двоичное дерево поиска Деревья

✓ 15✗ 10700средняяВойти и решать

Количество элементов в дереве#44646

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

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	9

Двоичное дерево поиска Деревья

✓ 33✗ 20500лёгкаяВойти и решать

Высота дерева#44645

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

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

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

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

Выведите единственное число – высоту получившегося дерева.

Пример соответствует следующему дереву:

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	4

Двоичное дерево поиска Деревья

✓ 30✗ 34500лёгкаяВойти и решать

Ускорители для Деда Мороза#44037

Дед Мороз за ночь должен посетить N городов. У него есть двумерный план расположения всех городов. План нарисован в декартовой системе координат, в которой точкой (0, 0) обозначено место старта Деда Мороза. Каждый город на плане отмечен точкой с координатой (X_i, Y_i). Также на карте обозначены M точек с координатами (P_i, Q_i), в которых расположены ускорители. Чтобы успеть разнести все подарки, Дед Мороз может воспользоваться ускорителем, который увеличивает его скорость в два раза (а может им и не пользоваться).

Дед Мороз в Новогоднюю ночь начинает с места старта, посещает все N городов и возвращается обратно.

Начальная скорость Деда Мороза равна 1. Найдите наименьшее время, необходимое Деду Морозу, чтобы посетить все города и вернуться обратно. Временем, при котором он раскладывает все подарки будем пренебрегать!

Входные данные
Первая строка входных данных содержит два целых числа N и M (1 <= N <= 12, 0 <= M <=5). Следующие N строк содержат координаты городов (X_i, Y_i). Далее идут M строк с координатами ускорителей (P_i, Q_i). Все координаты различны и среди них нет координаты (0, 0).

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	2 1 1 1 0 1 1 0	2 1 1 1 0 1 1 0	Вот один из оптимальных способов разнести все подарки Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1. Пройти расстояние 1 от ускорителя 1 до города 1 со скоростью 2, затратив время 0,5. Пройти расстояние 1 от города 1 до города 2 со скоростью 2, затратив время 0,5. Пройти расстояние 1 от города 2 до начала координат со скоростью 2, затратив время 0,5.
2	2 1 1 1 0 1 100 0	3.4142135624	Вот один из оптимальных способов разнести все подарки Пройти расстояние 1.41... от начала координат до города 1 со скоростью 1, затратив время 1.41.... Пройти расстояние 1 от города 1 до города 2 со скоростью 1, затратив время 1. Пройти расстояние 1 от города 2 до начала координат со скоростью 1, затратив время 1.
3	1 2 4 4 1 0 0 1	4.3713203436	Вот один из оптимальных способов разнести все подарки Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1. Пройти расстояние 1,41... от ускорителя 1 до ускорителя 2 со скоростью 2, затратив время 0,707.... Пройти расстояние 5 от ускорителя 2 до города 1 со скоростью 4, затратив время 1,25. Пройти расстояние 5,65... от города 1 до начала координат со скоростью 4, затратив время 1,41....

Алгоритмы на графах Динамическое программирование на таблицах Элементарная геометрия

✓ 2✗ 181 300средняяВойти и решать

Схема дорог#44035

Дед Мороз составляет схему дорог, по которой можно будет кратчайшим образом посетить N городов. Для простоты он пронумеровал все города номерами 1,..., N. Города соединены M количеством дорог. I-я дорога (1<=i<=M) соединяет город A_i и город B_i. Прежде чем построить оптимальный маршрут Дед Мороз хочет знать с какими городами связан каждый город. Помогите Деду Морозу.
Выведите N строк следующим образом.

Пусть d_i - количество городов, непосредственно связанных с городом i (1<=i<=N), и этими городами будут города a_i,1, ..., a_i,di,перечисленных в порядке возрастания.
I-я строка (1<=i<=N) должна содержать d_i+1 целое число: d_i, a_i,1,...,a_i,di в указанном порядке, разделенные пробелами.

Входные данные
Первая строка входных данных содержит два целых числа, разделенных одним пробелом N и M (2 <= N <= 10⁵, 1 <= M <= 10⁵). Далее следует M строк, каждая из которых содержит 2 числа A_i и B_i(1 <= A_i < B_i <= N, 1 <= i <= M).
Если i≠j, то (A_i, B_i)≠(A_j, B_j). Все числа целые.

Выходные данные
Выведите N строк по формату, описанному в условии задачи.

Примеры

№	Входные данные	Выходные данные
1	6 6 3 6 1 3 5 6 2 5 1 2 1 6	3 2 3 6 2 1 5 2 1 6 0 2 2 6 3 1 3 5
2	5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5	4 2 3 4 5 4 1 3 4 5 4 1 2 4 5 4 1 2 3 5 4 1 2 3 4

Способы задания графа

✓ 15✗ 23900средняяВойти и решать

Короткий код#40164

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

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

Строка a является префиксом строки b, если вы можете удалить несколько (возможно, ни одного) символа с конца строки b и получить a.

Найдите минимальную возможную суммарную длину новых имён.

Входные данные:
В первой строке содержится одно целое число n (1 ≤ n ≤ 10⁵) — число переменных в коде Эвана.

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

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

Примеры:

Входные данные	Выходные данные
3 codeforces codehorses code	6
5 abba abb ab aa aacada	11
3 telegram digital resistance	3

Пояснения:
В первом примере одним из наилучших вариантов будет сокращение имён в порядке их ввода до "cod", "co", "c".
Во втором примере можно укоротить последнее имя до "aac" и первое имя до "a" без изменения других имён переменных.

Бор Деревья Жадный алгоритм

✓ 1✗ 101 200средняяВойти и решать

Игра со строками#40161

Дана игра для двоих игроков со строками.

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

По задданому набору строк определите, кто будет победителем, если оба игрока будут играть оптимально.

Входные данные:
Первая строка содержит целое число n (1 ≤ n ≤ 10⁵).
Каждая из n следующих строк содержит непустую строку из заданного набора. Суммарная длина всех строк из набора не превышает 10⁵. Все строки из набора состоят только из строчных латинских букв.

Выходные данные:
Если победит игрок, который ходит первым, то выведите «First», иначе выведите «Second» (кавычки выводить не нужно).

Примеры:

Входные данные	Выходные данные
3 a b c	First
1 ab	Second

Бор Игры и выигрышные стратегии Обход в глубину

✓ 3✗ 11 000средняяВойти и решать

Бункеры#39676

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

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

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

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

Входные данные:
В первой строке входного файла находится одно целое число n (1 <= n <= 10⁵) - количество бункеров.
В следующих n - 1 строках находится по два целых числа u_i и v_i (1 <= u_i, v_i <= n, u_i ≠ v_i) - номера бункеров, которые соединяет i-ый тоннель.
Гарантируется, что между любыми двумя бункерами существует единственный путь.

Выходные данные:
В выходной файл выведите "YES", если можно выбрать штаб-квартиру и нарисовать такой план, или "NO" если это невозможно.

Примеры:

Входные данные	Выходные данные
2 1 2	NO
3 1 2 2 3	YES

Деревья Хеш

✓ 1✗ 61 000средняяВойти и решать

Странный сон Константина#39670

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

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

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

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

Входные данные:
В первой строке записано число n - количество запросов на добавление новой вершины в дерево (1 <= n <= 300000).
В следующих n строках описаны запросы добавления вершин. i-ый запрос описывается параметрами p_i (1 <= p_i <= i) и c_i, которые означают, что добавленная вершина с номером i+1 подвешивается к вершине с номером p_i в качестве потомка, а на полученном ребре записывается символ c_i - строчная буква латинского алфавита.

Выходные данные:
Выведите n строк. В i-ой строке выведите ответ на задачу Константина после добавления i+1-ой вершины.

Примеры:

Входные данные	Выходные данные
2 1 b 2 p	1 2
3 1 o 1 o 2 j	1 1 2

Бор Деревья Хеш

✓ 59✗ 360500лёгкаяВойти и решать

Танцевальные движения#39575

Коровы Фермера Джона танцуют.
Сначала все N коров (2≤N≤10⁵) стоят в ряд и корова i находится на позиции i. Последовательность танцевальных движений задаётся K (1≤K≤2⋅10⁵) парами позиций (a₁,b₁),(a₂,b₂),…,(a_K,b_K). Каждую минуту i=1…K танца коровы на позициях a_i и b_i меняются местами. Такие же K обменов делаются на минутах K+1…2K, затем опять на минутах 2K+1…3K, и т.д. Другими словами,

на минуте 1 меняются местами коровы на позициях a₁ и b₁.
на минуте 2 меняются местами коровы на позициях a₂ и b₂.
...
На минуте K меняются местами коровы на позициях a_K и b_K swap.
На минуте K+1, меняются местами коровы на позициях a₁ и b₁.
На минуте K+1, меняются местами коровы на позициях a₂ и b₂.
и т.д. ...
Для каждой коровы определите количество уникальных позиций, которые она посетит во время бесконечного танца.

Входные данные
Первая строка ввода содержит целые числа N и K. Каждая из последующих K строк содержит (a₁,b₁)…(a_K,b_K) (1≤a_i<b_i≤N).
Выходные данные
Выведите N строк, где i-ая строка содержит количество уникальных позиций, которые посетит корова i.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 4 1 3 1 2 2 3 2 4	4 4 3 4 1	Корова 1 достигнет позиций {1,2,3,4}. Корова 2 достигнет позиций {1,2,3,4}. Корова 3 достигнет позиций {1,2,3}. Корова 4 достигнет позиций {1,2,3,4}. Корова 5 не будет двигаться, и не покинет позицию 5.

Обход в глубину Перестановки

✓ 1✗ 11 100средняяВойти и решать

Часовое дерево#39505

Новый амбар Фермера Джона состоит из N комнат (2 ≤ N ≤ 2500), последовательно пронумерованных 1…N, и N−1 коридоров. Каждый коридор соединяет пару комнат таким образом, что возможно пройти из лбой комнаты в любую через серию коридоров.
Каждая комната в амбаре имеет круглые часы на стене со стандартным размещением цифр 1…12 на лицевой стороне. Однако на этих часах имеется только одна стрелка, которая всегда показывает точно на одно из целых чисел (она никогда не показывает между двумя из этих чисел).

Корова Беси хочет синхронизировать все часы в амбаре, чтобы они все показывали на число 12. Но со своим коровьим мышлением, каждый раз, когда она входит в комнату, она перемещает стрелку вперёд на одну позицию. Например, если стрека показывала на 5, Беси переводит стрелку на 6. Если часы указывали на 12, она переводит стрелку на 1. Если Беси входит в комнату несколько раз, она переводит стрелку при каждом входе.

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

Входные данные
Первая строка ввода содержит N. Следующая строка содержит N целых чисел, каждое в интервале 1…12, указывающих начальные положения стрелок в каждой комнате. Каждая из следующих N−1 строк описывает коридор двумя целыми числам a и b, каждое в интервале 1…N, и задающих номера комнат, соединённых этим коридором.

Выходные данные
Выведите номера комнат, в которых Беси может начинать, чтобы установить все часы на 12.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 11 10 11 11 1 2 2 3 2 4	1	В этом примере Беси может установить все стрелки на 12, тоько в том случае, если она начнёт в комнате 2 (например перемещаясь так: 1, 2, 3, 2, 4.

Вывод формулы Обход в глубину

✓ 2✗ 21 100средняяВойти и решать

Раскраска в три цвета#38919

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

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

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

Входные данные
В первой строке вводятся два целых числа n и m – количество кружков и количество линий, которые нарисовал Петя, соответственно (1 ≤ n ≤ 1 000, 0 ≤ m ≤ 20 000).
Следующая строка содержит n символов из множества {'R', 'G', 'B'} – i-й из этих символов означает цвет, в который раскрашен i-й кружок ('R' – красный, 'G' – зеленый, 'B' – синий).
Далее в m строках задается по два целых числа – пары кружков, соединенных отрезками.

Выходные данные
Выведите одну строку, состоящую из n символов из множества {'R', 'G', 'B'} – цвета кружков после перекраски. Если решений несколько, выведите любое.
Если решения не существует, выведите слово "Impossible''.

Примеры

№	Входные данные	Выходные данные
1	4 5 RRRG 1 3 1 4 3 4 2 4 2 3	BBGR
2	4 5 RGRR 1 3 1 4 3 4 2 4 2 3	Impossible

Обход в глубину Простые задачи на перебор

✓ 25✗ 1041 100средняяВойти и решать

Коровы#38846

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

Входные данные
В первой строке входного файла записано число досок N (0 <= N <= 1000). Далее для каждой доски записаны координаты кочек - концов доски (-2³¹ <= X_i,Y_i <= 2³¹). Затем записаны координаты начальной и конечной точек (точки различны и доски, их соединяющей нет). Все числа во входном файле целые.

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

Примеры

№	Входные данные	Выходные данные
1	8 0 0 1 0 1 0 2 1 1 0 2 -1 2 1 3 0 2 -1 3 0 1 0 4 0 3 0 4 0 0 0 3 0 0 0 4 0	2

Потоки

✓ 6✗ 30800средняяВойти и решать

Премьер министр#38845

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

Входные данные
В первой строке входного файла находятся числа N - количество российских городов, соединенных железными дорогами в единую сеть и М - количество железнодорожных перегонов, соединяющих пары городов (1 <= N <= 20000, 1 <= M <= 200000). Города имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя городами проходит соответствующая железнодорожная ветка. В последней строке находятся два целых числа S и Е (1 <= S != E <= N) - номера Москвы и Владивостока по версии РЖД.

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

Примеры

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

Обход в глубину

✓ 6✗ 52800средняяВойти и решать

Одностороннее движение#38844

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

Входные данные
В первой строке входного файла находятся числа N - количество площадей в городе и М - количество улиц их соединяющих (1 <= N <= 20000, 1 <= M <= 200000). Площади имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя площадями проходит соответствующая улица (две площади соединяются не более чем одной улицей).

Выходные данные
На первой строке выведите число B - количество улиц, на которых организовать одностороннее движение невозможно. На следующей строке выведите B целых чисел - номера этих улиц в возрастающем порядке. Улицы нумеруются с единицы в том порядке, в котором они заданы во входном файле.

Примеры

№	Входные данные	Выходные данные
1	10 16 2 6 3 7 6 5 5 9 5 4 1 2 9 8 6 4 2 10 3 8 7 9 1 4 2 4 10 5 1 6 6 10	1 4

Обход в глубину

✓ 2✗ 8—Войти и решать

Бусинки#38843

Маленький мальчик делает бусы. У него есть много пронумерованных бусинок. Каждая бусинка имеет уникальный номер - целое число в диапазоне от 1 до N. Он выкладывает все бусинки на полу и соединяет бусинки между собой произвольным образом так, что замкнутых контуров не образуется. Каждая из бусинок при этом оказывается соединенной с какой-либо другой бусинкой. Требуется определить, какое максимальное количество последовательно соединенных бусинок присутствует в полученной фигуре.

Входные данные
В первой строке записано число N (1 ≤ N ≤ 2500) - количество бусинок . В последующих N - 1 строках по два целых числа - номера, соединенных бусинок.

Выходные данные
Вывести одно число - искомое количество бусинок.

Примеры

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

Обход в глубину

✓ 70✗ 284800средняяВойти и решать

Спелестология#38838

Спелестологический клуб «Залезь и посмотри» часто привлекается к поиску заблудившихся в каменоломнях незадачливых путешественников. Заблудившиеся в темноте и тесноте паникуют, хаотично перемещаются, ходят кругами и осложняют этим поисковые работы. Гораздо удобнее было бы, если бы потерявшиеся сидели в каком-нибудь зале и никуда не двигались.
Каменоломни представляют собой набор из N залов, занумерованных числами от 1 до N и M проходов между ними. Проходы могут быть как двусторонними, так и односторонними (например, с сильным вертикальным уклоном). Ни один проход не соединяет зал сам с собой. Пара залов может соединяться максимум одним проходом. Гарантируется, что двигаясь только по односторонним проходам, нельзя попасть в тот зал, из которого вышли путешественники.
Чтобы избежать хождения заблудившихся по кругу, члены клуба решили нанести на двусторонние проходы специальные аварийные стрелки так, чтобы идя по этим стрелкам нельзя было попасть в уже посещенное место, откуда бы ни началось движение и, в итоге, потерявшиеся оказались бы в одном из залов, из которого нельзя уйти, двигаясь по стрелочкам — там их и найдут спелестологи.
Для каждого двустороннего прохода определите допустимое направление движения.

Формат входных данных
В первой строке входных данных задается два числа N (2 ≤ N ≤ 100000) и M (1 ≤ M ≤ 100000) — количество залов и проходов между ними.
В следующих M строках задаются описания проходов. Каждое описание состоит из трёх чисел A, B и D (1 ≤ A, B ≤ N). Числа A и B задают номера соединенных проходом залов. Если D = 1, то проход односторонний из зала A в зал B. Если D = 2, то проход двусторонний.

Формат выходных данных
Для каждого двустороннего прохода из входных данных выведите пару чисел, описывающих соединяемые этим проходом залы. Движение может осуществляться из первого зала во второй.
Если правильных ответов несколько — выведите любой из них. Порядок вывода описания проходов не важен. Гарантируется, что ответ всегда существует.

Примеры

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

Обход в глубину

✓ 4✗ 21 000средняяВойти и решать