Дан ориентированный ацикличный граф из $$$n$$$ вершин и $$$m$$$ ребер. В графе отсутствуют петли и кратные ребра.
Необходимо разбить все ребра этого графа на гамильтоновы циклы (циклы, проходящие по каждой из $$$n$$$ вершин графа ровно по одному разу) так, чтобы каждое ребро принадлежало ровно одному циклу. Очевидно, для исходного графа это невозможно, поэтому перед разбиением вы должны добавить в граф минимальное количество ребер так, чтобы такое разбиение существовало.
После добавления ребер в графе могут быть циклы и/или кратные ребра, но все еще не должно быть петель.
В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 100$$$; $$$1 \le m \le \frac{n(n-1)}{2}$$$).
Далее следуют $$$m$$$ строк, в $$$i$$$-й из которых заданы два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$), означающих ориентированное ребро из вершины $$$x_i$$$ в вершину $$$y_i$$$.
Дополнительные ограничения на входные данные:
В первой строке выведите одно целое число $$$k$$$ ($$$1 \le k \le n \cdot m$$$) — количество ребер, которые вы добавляете.
Далее выведите $$$k$$$ строк, в $$$i$$$-й из которых должны быть два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$), обозначающих начало и конец очередного ребра.
Затем в единственной строке выведите одно целое число $$$c$$$ ($$$1 \le c \le m$$$) — количество гамильтоновых циклов, на которые вы разбиваете все ребра графа.
В последней строке выведите $$$m+k$$$ целых чисел $$$a_1, a_2, \dots, a_{m+k}$$$ ($$$1 \le a_i \le c$$$), где $$$a_i$$$ — гамильтонов цикл, которому вы назначаете $$$i$$$-е ребро (ребра исходного графа нумеруются от $$$1$$$ до $$$m$$$, а новые — от $$$m+1$$$ до $$$m+k$$$).
Если ответов, минимизирующих количество добавленных ребер, несколько, выведите любой из них.
3 21 22 3
1 3 1 1 1 1 1
5 41 23 23 45 4
6 2 3 4 5 5 1 1 5 2 1 4 3 2 1 2 1 2 1 1 1 2 2 2
4 61 22 44 31 32 31 4
6 3 1 4 2 3 1 3 2 2 4 4 1 3 1 1 1 3 2 2 1 2 2 3 3 3
| Kotlin Heroes: Episode 12 |
|---|
| Закончено |
