8999: Fine Logic

内存限制:128 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:9 通过:7

题目描述


We consider a set GGG consisting of nnn entities and the relations on GGG. For simplicity, these nnn entities are labeled from 111 to nnn.
The ranking RRR on GGG is defined as an nnn-order permutation R=r1,r2,…rnR = r_1,r_2,\dots r_nR=r1,r2,rn (1≤ri≤n1\leq r_i\leq n1rin).
The winning relation on GGG is defined as an ordered pair ⟨u,v⟩\langle u, v\rangleu,v (1≤u,v≤n1\leq u,v\leq n1u,vn, u≠vu\neq vu=v), representing that the entity uuu wins in the competition with the entity vvv.
We say that the ranking RRR satisfies the winning relation ⟨u,v⟩\langle u, v\rangleu,v if and only if there exist 1≤i<j≤n1\leq i<j\leq n1i<jn such that ri=ur_i=uri=u and rj=vr_j=vrj=v.
Given the number of entities nnn, and mmm winning relations, you are required to construct the minimal number of rankings such that each winning relation is satisfied by at least one ranking in the constructed rankings.

输入格式


The first line contains two positive integers n,mn, mn,m (2≤n≤1062\leq n\leq 10^62n106, 1≤m≤1061\leq m\leq 10^61m106), representing the number of entities, and the number of winning relations.
Each of the following mmm lines contains two positive integers u,vu, vu,v (1≤u,v≤n1\leq u, v\leq n1u,vn, u≠vu\neq vu=v), representing a winning relation ⟨u,v⟩\langle u, v\rangleu,v.

输出格式


The first line contains a positive integer kkk, representing the minimal number of rankings needed.
Each of the following kkk lines contains nnn integers ri1,ri2,…rinr_{i1}, r_{i2}, \dots r_{in}ri1,ri2,rin (1≤rij≤n1\leq r_{ij}\leq n1rijn), representing the iii-th ranking Ri=ri1,ri2,…rinR_i = r_{i1}, r_{i2}, \dots r_{in}Ri=ri1,ri2,rin.

输入样例 复制

6 4
1 4
2 3
5 6
5 3

输出样例 复制

1
2 5 1 6 3 4