← 返回题目列表

Codeforces · 2087/I

I. 哈密顿划分

中文机器翻译题面 查看原题

给你一个有向无环图,其中有 $$$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 2
1 2
2 3

输出
复制

1
3 1
1
1 1 1 

输入
复制

5 4
1 2
3 2
3 4
5 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 6
1 2
2 4
4 3
1 3
2 3
1 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