8999: Fine Logic

We consider a set $G$ consisting of $n$ entities and the relations on $G$. For simplicity, these $n$ entities are labeled from $1$ to $n$.
The ranking $R$ on $G$ is defined as an $n$-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 $G$ 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\ne v$), representing that the entity $u$ wins in the competition with the entity $v$.
We say that the ranking $R$ satisfies 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 $n$, and $m$ 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,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 $m$ lines contains two positive integers u,vu, vu,v (1≤u,v≤n1\leq u, v\leq n1≤u,v≤n, $u\ne v$), representing a winning relation ⟨u,v⟩\langle u, v\rangle⟨u,v⟩.

The first line contains a positive integer $k$, representing the minimal number of rankings needed.
Each of the following $k$ lines contains $n$ 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 $i$-th ranking Ri=ri1,ri2,…rinR_i = r_{i1}, r_{i2}, \dots r_{in}Ri=ri1,ri2,…rin.