Məsələlər
Самый длинный путь
Самый длинный путь
В ориентированном графе найдите самый длинный путь такой, что каждая вершина графа встречается в нём не более одного раза.
Giriş verilənləri
В первой строке заданы два целых числа n и m (1 ≤ n ≤ 22, 0 ≤ m ≤ 1000). В следующих 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