CF2087I Hamiltonian Partition

给定一个有 $n$ 个顶点和 $m$ 条边的有向无环图。该图不包含环或重边。 你需要将该图的所有边划分为若干个哈密顿环（即每个环恰好经过图中的每一个顶点一次），使得每条边恰好属于一个环。显然，原图无法满足这一要求，因此你需要在划分之前，向图中添加最少数量的边，使得这样的划分成为可能。 添加边后，图中可以出现环和重边，但不能有自环。

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 100$；$1 \le m \le \frac{n(n-1)}{2}$）。 接下来的 $m$ 行，每行包含两个整数 $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$ 行，每行两个整数 $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$）被分配到的哈密顿环编号。 如果存在多种添加边数最少的方案，输出任意一种均可。

由 ChatGPT 4.1 翻译