В городе, построенном во времена средневековья, ширина улиц стала препятствовать движению транспорта, которое изначально было двусторонним по каждой из улиц. Для решения этой проблемы было предложено сделать движение по каждой из улиц односторонним. Мэр поручил эту задачу своему первому заму. После долгих размышлений тот доложил, что на некоторых улицах движение придется оставить двусторонним, в противном случае будет невозможно проехать из любого места в городе в любое другое. По данной схеме города требуется найти все такие улицы.
В первой строке входного файла находятся числа N - количество площадей в городе и М - количество улиц их соединяющих \(1 \leq N \leq 20000, 1 \leq M \leq 200000\). Площади имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя площадями проходит соответствующая улица (две площади соединяются не более чем одной улицей).
На первой строке выведите число B - количество улиц, на которых организовать одностороннее движение невозможно. На следующей строке выведите B целых чисел - номера этих улиц в возрастающем порядке. Улицы нумеруются с единицы в том порядке, в котором они заданы во входном файле.
| Ввод | Вывод |
|---|---|
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 |
Вам дан неориентированный граф с \(n\) вершинами и \(m\) ребрами, не содержащий петель и кратных ребер. Найдите количество ребер графа, через которые можно провести цикл.
В первой строке через пробел записаны два целых числа \(n\) и \(m\) (\(1 \le n \le 100; 0 \le m \le {n \cdot (n-1) \over 2}\)) --- количество вершин и ребер графа. В следующих \(m\) строчках записано по два целых числа \(a\) и \(b\) (\(1 \le a,b \le n; a \neq b\)) --- номера вершин, которые соединяет описываемое ребро.
Выведите единственное число --- максимальное количество ребер графа, через которые можно провести цикл.
| Ввод | Вывод |
|---|---|
4 3 1 2 2 3 3 4 |
0 |
4 4 1 2 2 3 1 3 3 4 |
3 |
Дан неориентированный граф. Требуется найти все точки сочленения в нём.
Первая строка входного файла содержит два натуральных числа \(n\) и \(m\) — количества вершин и рёбер графа соответственно (\(1 \le n \le 20\,000\), \(1 \le m \le 200\,000\)).
Следующие \(m\) строк содержат описание рёбер по одному на строке. Ребро номер \(i\) описывается двумя натуральными числами \(b_i\), \(e_i\) — номерами концов ребра (\(1 \le b_i, e_i \le n\)).
Первая строка выходного файла должна содержать одно натуральное число \(b\) — количество точек сочленения в заданном графе. На следующей строке выведите \(b\) целых чисел — номера вершин, которые являются точками сочленения, в возрастающем порядке.
| Ввод | Вывод |
|---|---|
9 12 1 2 2 3 4 5 2 6 2 7 8 9 1 3 1 4 1 5 6 7 3 8 3 9 |
3 1 2 3 |
Новый премьер-министр решил проехать по России от Москвы до Владивостока по железной дороге, а затем вернуться обратно. Он поручил своим помощникам разработать маршрут так, чтобы не пришлось два раза проезжать через один и тот же город. Однако помощники сообщили, что для Российских железных дорог это невозможно. Определите, в каких городах премьер-министр будет вынужден побывать дважды.
В первой строке входного файла находятся числа N - количество российских городов, соединенных железными дорогами в единую сеть и М - количество железнодорожных перегонов, соединяющих пары городов \(1 \leq N \leq 20000, 1 \leq M \leq 200000\). Города имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя городами проходит соответствующая железнодорожная ветка. В последней строке находятся два целых числа S и Е \(1 \leq S != E \leq N\) - номера Москвы и Владивостока по версии РЖД.
В первой строке выведите число B - количество городов, которые премьер-министру придется посетить дважды. В следующих В строках выведите B целых чисел - номера этих городов в возрастающем порядке.
| Ввод | Вывод |
|---|---|
3 2 1 2 2 3 3 1 |
1 2 |
4 4 1 2 2 3 2 4 1 4 4 1 |
0 |
Добавить в граф G = ( V , E ) (возможно несвязный) ровно одно ребро, так чтобы количество мостов стало минимально возможным.
Первая строка входного файла содержит два натуральных числа n и m — количества вершин и рёбер графа соответственно ( 1 ≤ n ≤ 20000, 1 ≤ m ≤ 200000 ).
Следующие m строк содержат описание рёбер по одному на строке. Ребро номер i описывается двумя натуральными числами b i , e i — номерами концов ребра ( 1 ≤ b i , e i ≤ n ).
Выведите наименьшее число мостов, которое можно получить добавлением ровно одного ребра.
| Ввод | Вывод |
|---|---|
6 7 1 2 2 3 3 4 1 3 4 5 4 6 5 6 |
0 |
Город будущего застроен небоскребами, для передвижения между которыми и парковки транспорта многие тройки небоскребов соединены треугольной подушкой из однополярных магнитов. Каждая подушка соединяет ровно 3 небоскреба и вид сверху на нее представляет собой треугольник, с вершинами в небоскребах. Это позволяет беспрепятственно передвигаться между соответствующими небоскребами. Подушки можно делать на разных уровнях, поэтому один небоскреб может быть соединен различными подушками с парами других, причем два небоскреба могут соединять несколько подушек (как с разными третьими небоскребами, так и с одинаковым). Например, возможны две подушки на разных уровнях между небоскребами 1, 2 и 3, и, кроме того, магнитная подушка между 1, 2, 5.
Система магнитных подушек организована так, что с их помощью можно добираться от одного небоскреба, до любого другого в этом городе (с одной подушки на другую можно перемещаться внутри небоскреба), но поддержание каждой из них требует больших затрат энергии.
Требуется написать программу, которая определит, какие из магнитных подушек нельзя удалять из подушечной системы города, так как удаление даже только этой подушки может привести к тому, что найдутся небоскребы из которых теперь нельзя добраться до некоторых других небоскребов, и жителям станет очень грустно.
В первой строке входного файла находятся числа \(N\) и \(M\) — количество небоскребов в городе и количество работающих магнитных подушек соответственно \((3 \leq N \leq 100000, 1 \leq M \leq 100000)\). В каждой из следующих \(M\) строк через пробел записаны три числа — номера небоскребов, соединенных подушкой. Небоскребы пронумерованы от 1 до \(N\). Гарантируется, что имеющиеся воздушные подушки позволяют перемещаться от одного небоскреба до любого другого.
Выведите в выходной файл сначала количество тех магнитных подушек, отключение которых невозможно без нарушения сообщения в городе, а потом их номера. Нумерация должна соответствовать тому порядку, в котором подушки перечислены во входном файле. Нумерация начинается с единицы.
| Ввод | Вывод |
|---|---|
3 1 1 2 3 |
1 1 |
3 2 1 2 3 3 2 1 |
0 |
Петя работает в межгалактическом агентстве путешествий. Он часто получает запросы на поиск пути между двумя планетами по доступным межпланетным дорогам. Петя уже сделал по этому поводу целый ряд наблюдений, и сейчас его интересует следующее. Для каждой планеты \(А\) он хочет знать количество пар планaет \(В\) и \(С\), таких что любой путь от планеты \(В\) к планете \(С\) проходит через планету \(А\).
Первая строка входного файла содержит два числа \(2 \leq N \leq 20000\) и \(1 \leq M \leq 200000\) – число планет и число дорог соответственно. Далее в \(M\) строках следуют описания дорог. По дорогам можно двигаться в обе стороны. Каждая дорога описывается номерами планет, которые она соединяет. Гарантируется, что от любой планеты можно добраться до любой другой.
В выходной файл выведите \(N\) чисел – для каждой планеты \(А\) выведите количество пар различных планет, таких что любой путь от одной до другой содержит \(А\).
| Ввод | Вывод |
|---|---|
7 9 1 2 1 3 1 4 1 5 1 6 1 7 2 3 4 5 6 7 |
18 6 6 6 6 6 6 |