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