33597번 - Condorcet Elections 스페셜 저지다국어

문제

It is a municipality election year. Even though the leader of the country has not changed for two decades, the elections are always transparent and fair.

There are $n$ political candidates, numbered from 1ドル$ to $n,ドル contesting the right to govern. The elections happen using a variation of the Ranked Voting System. In their ballot, each voter will rank all $n$ candidates from most preferable to least preferable. That is, each vote is a permutation of $\{1, 2, \dots , n\},ドル where the first element of the permutation corresponds to the most preferable candidate.

We say that candidate $a$ defeats candidate $b$ if in more than half of the votes candidate $a$ is more preferable than candidate $b$.

As the election is fair and transparent, the state television has already decreed a list of $m$ facts—the $i$-th fact being “candidate $a_i$ has defeated candidate $b_i$”—all before the actual election!

You are in charge of the election commission and tallying up the votes. You need to present a list of votes that produces the outcome advertised on television, or to determine that it is not possible. However, you are strongly encouraged to find a solution, or you might upset higher-ups.

입력

The first line contains integers $n$ and $m$ (2ドル ≤ n ≤ 50,ドル 1ドル ≤ m ≤ \frac{n(n-1)}{2}$) — the number of parties and the number of pairs with known election outcomes.

The $i$-th of the following $m$ lines contains two integers $a_i$ and $b_i$ (1ドル ≤ a_i , b_i ≤ n,ドル $a_i \ne b_i$) — candidate $a_i$ defeats candidate $b_i$.

Each unordered pair $\{a_i , b_i\}$ is given at most once.

출력

Print YES if there is a list of votes matching the facts advertised on television. Otherwise, print NO.

If there is a valid list of votes, print one such list in the following lines.

Print the number $k$ of votes cast (1ドル ≤ k ≤ 50,円 000$). It can be shown that if there is a valid list of votes, there is one with at most 50ドル,円 000$ votes.

Then print $k$ lines. The $i$-th of these lines consists of a permutation of $\{1, 2, \dots , n\}$ describing the $i$-th vote. The first number in the permutation is the most preferable candidate and the last one is the least preferable candidate.

For 1ドル ≤ i ≤ m,ドル $a_i$ shall appear earlier than $b_i$ in more than $k/2$ of the $k$ permutations. For pairs of candidates $\{a, b\}$ not appearing in the election requirements list, the outcome can be arbitrary, including neither of $a$ and $b$ defeating the other.

제한

힌트