eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Мстители

Мстители

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Нурлашко, Нурбакыт и Жора — члены последнего клана ниндзя, сражающегося против злого правления императора Рена. После сокрушительного поражения в открытом бою они решили разделить свою армию на три лагеря и начать партизанскую войну.

Нелепые реформы одного императора Рэна позволяют проезжать дороги между городами только в одном направлении. Также он выбрал разрешенные направления дорог таким образом, чтобы невозможно было начать движение и вернуться в один и тот же город после прохождения нескольких дорог.

Прямо сейчас клан решает, где разместить свои лагеря. Армия императора Рэна совершает регулярные набеги, осматривая какой-то путь. Если армия сокрушит все три лагеря во время рейда, клан не сможет перегруппироваться и проиграет войну. Помогите клану выбрать три города таким образом, чтобы не было пути, проходящего через все три города.

Входные данные

Первая строка содержит два числа n, m\:(1 \le n, m \le 10^6) — количество городов и дорог в империи. Следующие m строк содержат пары чисел v_i, u_i\:(1 \le v_i, u_i \le n), описывающие направленную дорогу от v_i к u_i.

Выходные данные

Выведите три числа — индексы городов, в которых клан должен разместить свои лагеря. Если нет таких трех городов, то выведите -1. Если существует несколько ответов, то выведите любой из них.

Пример

Входные данные #1
3 2
1 2
2 3
Выходные данные #1
-1
Входные данные #2
3 2
1 2
1 3
Выходные данные #2
2 3 1
Источник 2021 KBTU Open, Весна Казахстан, Алма-Ата, 30 мая, Задача K