您正在城市街道上组织一场自行车比赛。该城市有n个路口,其中一些路口通过道路连接;在每条道路上,您可以向任何方向移动。没有两条道路连接同一对交叉路口,也没有道路将交叉路口与其自身连接。
您希望比赛向职业运动员和自行车初学者开放,因此您将以三种提名方式组织比赛:简单、中等和困难;每位参与者将选择更合适的提名。对于每个提名,您必须选择路线——由道路连续连接的交叉路口链。路线必须满足以下条件:
- 所有三条路线应在同一路口起点,并在同一路口终点(起点和终点不能相同);
- 为了避免碰撞,两条路线不能有共同的路口(共同的起点和终点除外),并且不能沿着同一条道路行驶(无论这两条路线在道路上的行驶方向如何);
- 任何路线不得两次经过同一路口或两次访问同一条道路(无论第一次和第二次访问时道路上的行驶方向如何)。
比赛准备工作即将开始,您需要尽快确定比赛路线。路线的长度并不重要,重要的是满足所有给定的要求。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 2·105) — 分别是交叉口和道路的数量。
接下来的 m 行包含两个整数——一条道路所连接的路口的编号(路口编号从 1 开始)。保证每对交叉路口仅由不超过一条道路连接,并且没有道路将交叉路口与其自身连接。
请注意,我们不保证您可以通过道路从任一路口到达任何其他路口。
输出
如果可以创建路线,请在第一行打印“YES”。在接下来的三行中,以“l p1 ... pl”的格式打印三条路线中每条路线的描述,其中 l 是路线中交叉路口的数量,p1, ..., pl 是按其遵循的顺序排列的数字。路由必须满足声明中指定的所有要求。
如果无法按照要求制定路线,则打印NO。
示例
输入 #1
4 4 1 2 2 3 3 4 4 1
输出 #1
NO
输入 #2
5 6 1 2 1 3 1 4 2 5 3 5 4 5
输出 #2
YES 3 5 4 1 3 5 3 1 3 5 2 1