Лишние ребра
Лишние ребра
Рассмотрим ориентированный граф G, состоящий из n вершин и m ориентированных ребер. Вершины пронумерованы от 1 до n, а ребра от 1 до m. Давайте выберем некоторую вершину r как начальную и найдем все вершины, достижимые из r в результате движения по ребрам (определим это множество как C0
). Определим C(e) как множество всех вершин, достижимых из r по ребрам кроме одного с номером e. Ребро e назовем лишним, если C(e) равно C0
.
Задан граф G и начальная вершина r. Найдите все лишние ребра.
Входные данные
Первая строка содержит три числа n, m и r (1 ≤ n ≤ 100000, 1 ≤ m ≤ 200000, 1 ≤ r ≤ n): количество вершин, количество ребер и начальную вершину. Следующие m строк описывают ребра графа: i-ая из них содержит два числа ai
и bi
(1 ≤ ai
, bi
≤ n) задающие ориентированное ребро от вершины ai
к bi
. Гарантируется отсутствие циклов, а для любых двух вершин u и v существует не более одного ребра от u к v.
Выходные данные
В первой строке вывести количество лишних ребер. Во второй строке вывести номера всех лишних ребер в произвольном порядке. Ребра стартуют с 1 в соответствии с порядком на входе.
3 3 1 1 2 2 3 3 1
1 3
4 6 2 2 1 2 3 3 1 3 4 1 4 4 2
5 1 3 4 5 6