Задача А. Правильное управление
Задачу добавил: alef
Успешно сдано решений: 25
ПредысторияМного лет тому вперед в одной Очень Большой Корпорации был (хотя, наверное, еще будет:)) Очень Мудрый Руководитель. Мудрость его столь велика, что никто из его подчиненных даже не пытается постичь его мудрые решения. Раньше, бывало, случалось, что кому и покажется, что какое-то решение недостаточно мудрое, а пройдет день или два, и Очень Мудрый Руководитель примет еще одно мудрое решение. И тут уж всем становится понятно, что предыдущее решение было очень даже мудрое, а если что и казалось - так это лишь потому, что никто и подумать не мог, что будет принято нынешнее.
Очень Большая Корпорация занимается всем, что связано с компьютерами, если выражаться современным языком. Конечно, понятно, что нам трудно представить себе, что эти устройства, производимые с применением йоктотехнологий (йокто = 10^-24), трансформирующиеся силой мысли и обладающие искуственным интеллектом, превосходящим интеллект кое-каких соседей по галактике, еще можно называть компьютерами, но мы все же будем использовать этот и другие современные нам термины, чтобы не отвлекаться каждый раз на рассказ, сколь далеко зашел прогресс.
Задача А. Правильное управление.
Ограничения: время на тест - 2с, память - 256 Мб
Очень Мудрый Руководитель считает, что корпорация должна работать по полному циклу - от добычи необходимых полезных ископаемых до розничной торговли. И решения принимает соответствующие. Например, однажды на совещании он узнал, что за последний месяц уже два раза наблюдались задержки поставок кобальта. Причем первая задержка составляла 38 наносекунд, а вторая, страшно подумать, 2 миллисекунды. Конечно, терпеть такое дальше было совершенно невозможно. И Очень Мудрый Руководитель принял решение приобрести небольшую безжизненную планету, обращающуюся возле звезды Пульхеррима (в созвездии Волопаса). Конечно, можно было бы приобрести шахту возле подводной горы на Земле, но Очень Мудрый Руководитель понимает, что производство постоянно растет, а запасов кобальта в шахте хватит от силы на пару миллионов лет.
В Очень Большой Корпорации дела ведутся таким образом, что ее подразделения обмениваются отчетами между собой. Разумеется, не все со всеми, а те, которые работают над каким-то общим проектом. И пока юристы Очень Большой Корпорации оформляют приобретение в Межгалактической Регистрационной Палате, Очень Мудрый Руководитель задумался, с каким из уже существующих подразделений должно быть связано вновь образованное подразделение по добыче кобальта. С одной стороны, есть Управление полезных ископаемых. С другой - кобальт используется только при производстве печатных плат нечеткой логики, и не будет ли более мудро, чтобы именно с ним новое подразделение обменивалось отчетами?
Очень Мудрый Руководитель поделился этими мыслями со своим Заместителем, на что тот воскликнул:
- Какие проблемы? Почему бы подразделению по добыче кобальта не обмениваться отчетами и с Управлением, и с Производством?
- Так не стоит делать, - спокойно заметил Очень Мудрый Руководитель. - Ведь тогда им придется готовить по два ежедневных отчета, а это лишние затраты человеко-секунд. Если Управлению полезными ископаемыми потребуется такой отчет, оно может запросить его через другие подразделения. А уж подразделению по добыче кобальта и вовсе нет необходимости каждый день получать статистику из Управления.
- Это не такие уж и большие затраты времени! - продолжал настаивать Заместитель. - То же Управление полезных ископаемых обменивается отчетами и с Управлением ресурсами, и с Управлением экологии, и еще с тремя или четырьмя Управлениями. Справляются же!
Очень Мудрый Руководитель промолчал и задумался о том, что, скорее всего, это не единичный случай в Очень Большой Корпорации. Спустя час на его столе лежал отчет о том, какие подразделения корпорации обмениваются между собой отчетами. Да, результат был неутешителен. В корпорации N подразделений. А вот связей между ними Очень Мудрый Руководитель насчитал целых M штук. И он полон решимости оставить минимальное количество связей между подразделениями, но так, чтобы структура осталась целостной и любое подразделение при необходимости могло получить доступ к отчету любого другого подразделения. Более того, поскольку Очень Мудрый Руководитель любит порядок во всем, он хочет, чтобы набор удаляемых связей был лексикографически минимальным.
Это означает, что необходимо удалить M - N + 1 связь между подразделениями. Именно это и нужно сделать Вам.
Гарантируется, что все связи различны и что никакое подразделение не связано непосредственно с самим собой. Также гарантируется, что имеющаяся структура связей обеспечивает возможность обмена отчетами между любыми двумя подразделениями.
Формат входного файла input.txt
Первая строка - два целых числа N и M (3 <= N <= 10^5, 3 <= M <= 10^5)- количество подразделений Очень Большой Корпорации и количество связей между ними.
Каждая из следующих M строк содержит по два целых числа i и j (1 <= i < j <= N), описывающих связь между подразделениями #i и #j.
Формат выходного файла output.txt
Каждая из M - N + 1 строк содержит одну пару вершин, определяющих удаленную связь.
Пары вершин должны быть упорядочены лексикографически, т.е.:
в паре: q < p (номер первой вершины меньше номера второй)
в списке: пара q1 p1 должна быть упомянута раньше, чем пара q2 p2, если либо q1 < q2, либо q1 = q2, но p1 < p2
Если существует несколько ответов, выведите лексикографически минимальный
Пример входного файла - 1:
6 9
1 2
2 5
1 3
2 3
2 4
4 5
3 4
3 6
4 6
Пример выходного файла - 1:
1 2
2 3
2 4
3 4
Пример входного файла - 2:
8 10
1 2
2 4
4 5
2 5
1 3
3 6
6 8
7 8
3 7
6 7
Пример выходного файла - 2:
2 4
3 6
6 7
Пример входного файла - 3:
4 4
1 3
2 3
2 4
3 4
Пример выходного файла - 3:
2 3
Пример входного файла - 4:
5 5
1 5
4 5
2 4
3 4
3 5
Пример выходного файла - 4:
3 4
Примечание.
Под лексикографически минимальным ответом понимается такой, что первая отличающаяся вершина любого другого ответа, упорядоченного так, как описано в формате выходного файла, имеет больший номер.