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 rankingRRR 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 n1≤ri≤n).
The winning relation on GGG is defined as an ordered pair ⟨u,v⟩\langle u, v\rangle⟨u,v⟩ (1≤u,v≤n1\leq u,v\leq n1≤u,v≤n, u≠vu\neq vu=v), representing that the entity uuuwins in the competition with the entity vvv.
We say that the ranking RRRsatisfies the winning relation ⟨u,v⟩\langle u, v\rangle⟨u,v⟩ if and only if there exist 1≤i<j≤n1\leq i<j\leq n1≤i<j≤n 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^62≤n≤106, 1≤m≤1061\leq m\leq 10^61≤m≤106), 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 n1≤u,v≤n, u≠vu\neq vu=v), representing a winning relation ⟨u,v⟩\langle u, v\rangle⟨u,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 n1≤rij≤n), representing the iii-th ranking Ri=ri1,ri2,…rinR_i = r_{i1}, r_{i2}, \dots r_{in}Ri=ri1,ri2,…rin.