eolymp
bolt
Try our new interface for solving problems
Məsələlər

Самый длинный путь

Самый длинный путь

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

В ориентированном графе найдите самый длинный путь такой, что каждая вершина графа встречается в нём не более одного раза.

Giriş verilənləri

В первой строке заданы два целых числа n и m (1n22, 0m1000). В следующих m строках заданы рёбра графа в формате u[i] v[i] - номера начальной и конечной вершин ребра i соответственно. Граф может содержать петли и кратные рёбра.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
3 3
1 2
2 3
3 1
Çıxış verilənləri #1
2
1 2 3
Giriş verilənləri #2
4 6
1 2
2 1
2 3
2 4
3 2
4 2
Çıxış verilənləri #2
2
1 2 3
Giriş verilənləri #3
5 3
3 2
2 2
1 5
Çıxış verilənləri #3
1
3 2
Müəllif Сергей Копелиович
Mənbə 2011 Зимняя школа, Харьков, День 5