The Meeting Place Cannot Be Changed
Contest: Codeforces Round 484 (Div. 2)
Difficulty rating: 2700
Tags: dfs and similar, graphs

Petr is a detective in Braginsk. Somebody stole a huge amount of money from a bank and Petr is to catch him. Somebody told Petr that some luxurious car moves along the roads without stopping.

Petr knows that it is the robbers who drive the car. The roads in Braginsk are one-directional and each of them connects two intersections. Petr wants to select one intersection such that if the robbers continue to drive the roads indefinitely, they will sooner or later come to that intersection. The initial position of the robbers is unknown. Find such an intersection that fits the requirements.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \le 10^5$$$, $$$2 \leq m \leq 5 \cdot 10^5$$$) — the number of intersections and the number of directed roads in Braginsk, respectively.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — the start and finish of the $$$i$$$-th directed road. It is guaranteed that the robbers can move along the roads indefinitely.

Output format:
Print a single integer $$$k$$$ — the intersection Petr needs to choose. If there are multiple answers, print any. If there are no such intersections, print $$$-1$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example the robbers can move, for example, along the following routes: $$$(1-2-3-1)$$$, $$$(3-4-5-3)$$$, $$$(1-2-3-4-5-3-1)$$$. We can show that if Petr chooses the $$$3$$$-rd intersection, he will eventually meet the robbers independently of their route.

Example input:
5 6
1 2
2 3
3 1
3 4
4 5
5 3

Example output:
3

Example input:
3 3
1 2
2 3
3 1

Example output:
1

Editorial:
Предположим, что решение существует, и будем искать решение исходя из этого предположения. В конце проверим найденное решение за линию, и если оно решением не является, то предположение было неверно.
Пусть решение существует. Значит пересечение всех циклов не пустое. Возьмём один любой цикл, который назовём главным. Можно представить его как окружность с направлением по часовой стрелке. Отметим на этой окружности все искомые вершины, принадлежащие всем циклам.
Рассмотрим только циклы, которые выходят из вершины главного цикла, приходят в какую-то вершину главного цикла, а дальше движутся по главному циклу и замыкаются. Если цикл выходит из главного цикла, то он должен на него вернуться где-то дальше по направлению главного цикла, при этом не перескакивая отмеченные вершины с ответом (иначе будет пустое пересечение, а мы предположили, что не пустое) (считаем, что если цикл вернулся не по главному циклу туда же, откуда вышел, то он совершил скачок длинной весь главный цикл, а не 0). От вершины, в которой рассматриваемый цикл возвращается на главный, до вершины, из которой он выходит с главного, проведём дугу в направлении главного цикла. Те вершины главного цикла, которые такая дуга не покрывает, заведомо не могут являться ответом. Пересечение всех рассмотренных циклов с главным определяется пересечением всех таких дуг.
Мы не рассмотрели только циклы, которые несколько раз выходят с главного и несколько раз возвращаются на главный цикл. Но пересечение такого цикла с главным циклом будет таким же, как если пересечь отдельные циклы между соседними выходом/возвратом. Поэтому такие сложные циклы можно не рассматривать.
Теперь нужно отметить все дуги между возвратом-выходом с главного цикла. Для этого будем запускать dfs из всех вершин главного цикла и пытаться вернуться на главный цикл как можно дальше (расстояние измеряется по количеству вершин главного цикла между выходом и возвратом). Как было отмечено выше, циклы, выходя и возвращаясь, не могут перескакивать ответ. Значит все dfs'ы, стартующие между границами ответов, стремятся к какой-то вершине главного цикла, которая является граничной в дуге с возможными ответами. Значит если в одном dfs'е мы выбрали самую удалённую вершину из нескольких вариантов, то в другом dfs'е рассматриваемые варианты не поменяются ролями, и старая самая удалённая вершина так и останется самой удалённой среди тех же вариантов в новом dfs'е. Значит можно запускать все dfs'ы с общим массивом used, в котором кэшировать самую удалённую вершину.
В итоге решение сводится к тому, чтобы найти главный цикл, отсортировать его вершины по направлению обхода, запустить из них из всех dfs’ы с общим массивом used’ов, между стартом и финишом всех dfs’ов отметить дуги и пересечь их все, на пересечении всех дуг взять ответ. Если после удаления вершины-ответа в графе не останется больше циклов, то это действительно ответ, а иначе предположение было не верно и ответа не существует.