今年是市政选举年。尽管国家领导人二十年来没有更换,但选举始终是透明和公平的。
有 $$$n$$$ 政治候选人,编号从 $$$1$$$ 到 $$$n$$$,争夺执政权。选举是通过以下方式进行的: 排名投票系统。在他们的选票中,每个选民将对所有 $$$n$$$ 候选人从最优选到最不优选进行排名。也就是说,每次投票都是 $$$\{1, 2, \ldots, n\}$$$ 的排列,其中排列的第一个元素对应于最优选的候选者。
如果在超过一半的选票中候选人 $$$a$$$ 比候选人 $$$b$$$ 更受欢迎,我们就说候选人 $$$a$$$ 击败了候选人 $$$b$$$。
由于选举公平透明,国家电视台已经颁布了一份$$$m$$$事实清单——第$$$i$$$事实是“候选人$$$a_i$$$击败了候选人$$$b_i$$$”——所有这些都是在实际选举之前!
你负责选举委员会并统计选票。您需要提供一份投票列表,以产生电视上广告的结果,或者确定这是不可能的。然而,我们强烈鼓励你找到解决方案,否则你可能会惹恼上级。
输入
第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 50$$$, $$$1 \le m \le \frac{n(n-1)}{2}$$$) - 政党数量和已知选举结果的配对数量。
以下 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$) — 候选人 $$$a_i$$$ 击败候选人 $$$b_i$$$。
每个无序对 $$$\{a_i, b_i\}$$$ 最多给出一次。
输出
如果存在与电视上公布的事实相符的选票列表,则打印 $$$\texttt{YES}$$$。否则,打印 $$$\texttt{NO}$$$。
如果有有效的投票列表,请在以下行中打印一个此类列表。
打印投票数 $$$k$$$ ($$$1 \le k \le 50\,000$$$)。可以证明,如果存在有效的投票列表,则最多有 $$$50\,000$$$ 票。
然后打印 $$$k$$$ 行。这些行中的第 $$$i$$$ 由描述第 $$$i$$$ 投票的 $$$\{1, 2, \ldots, n\}$$$ 排列组成。排列中的第一个数字是最优选的候选,最后一个数字是最不优选的候选。
对于 $$$1\le i\le m$$$,$$$a_i$$$ 在超过 $$$k{/}2$$$ 的 $$$k$$$ 排列中应早于 $$$b_i$$$ 出现。对于没有出现在选举要求列表中的一对候选人$$$\{a, b\}$$$,结果可以是任意的,包括$$$a$$$ 和$$$b$$$ 都不击败对方。
示例
输入复制
2 11 2
输出复制
YES 1 1 2
输入复制
3 31 22 33 1
输出复制
YES 3 1 2 3 2 3 1 3 1 2
注意
在 第二个样本,观察候选人 $$$1$$$ 击败候选人 $$$2$$$,因为它在三分之二的选民排列中走得更早,占所有选票的一半以上。同样,候选人 $$$2$$$ 击败候选人 $$$3$$$,候选人 $$$3$$$ 击败候选人 $$$1$$$。