J-Fine Logic_2026牛客五一集训派对day1

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

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 = r_1,r_2,\dots r_n$ ( $1\leq r_i\leq n$ ).

The winning relation on $G$ is defined as an ordered pair $\langle u, v\rangle$ ( $1\leq u,v\leq n$ , $u\neq v$ ), representing that the entity $u$ wins in the competition with the entity $v$ .

We say that the ranking $R$ satisfies the winning relation $\langle u, v\rangle$ if and only if there exist $1\leq i<j\leq n$ such that $r_i=u$ and $r_j=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\leq n\leq 10^6$ , $1\leq m\leq 10^6$ ), representing the number of entities, and the number of winning relations.

Each of the following $m$ lines contains two positive integers $u, v$ ( $1\leq u, v\leq n$ , $u\neq v$ ), representing a winning relation $\langle u, v\rangle$ .

输出描述:

The first line contains a positive integer $k$ , representing the minimal number of rankings needed.

Each of the following $k$ lines contains $n$ integers $r_{i1}, r_{i2}, \dots r_{in}$ ( $1\leq r_{ij}\leq n$ ), representing the $i$ -th ranking $R_i = r_{i1}, r_{i2}, \dots r_{in}$ .

示例1

输入

复制

输出

复制

1
2 5 1 6 3 4