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