绘制地形

CC带着测距仪走了三小时——每条通道都量了，每个转角都记了。回来时，笔记本上全是数字和草图。

"画好了。"她说，"但看不懂。"

"给我。"你说。

你把数字输进终端。屏幕上跳出一个三维模型——通道像血管一样交错，有些交叉，有些平行，有些绕成圈。

"这是个迷宫。"你说。

"看得出来。"CC说，"入口在哪？"

"找。"你说，"入口有特征——它连接的外部通道比内部多。"

你开始在模型上标度。每个交叉点，数它连了几条通道。连得越多，越可能是枢纽；连得越少，越可能是入口。

"这里。"你标出一个点，"只连了两条通道，但一条通向外部。"

"入口？"

"可能是。"你说，"但也可能是死胡同。"

"咋个分？"

"看平面图。"你说，"如果这张图能画在平面上，没有交叉——那入口就在边缘。如果有交叉，那交叉点里面藏着秘密。"

你开始算。把每个交叉点画成点，每条通道画成线。试着在平面上摆——左一点，右一点，上一点，下一点。

"不行。"你说，"有两条线交叉了。"

"那咋办？"

"改。"你说，"把其中一个交叉点拆开，变成两个点，中间加一条短线。"

"拆开？"

"对。"你说，"就像把打结的绳子解开——不是剪断，是找到结头，慢慢松。"

你拆了三次，平了。屏幕上显示出一张干净的平面图——七条线，五个点，没有交叉。

"入口。"你标出最边缘的点，"在这里。"

CC看着那个点——在模型的最下方，像一张嘴，微微张开。

"就是这里。"她说。

"对。"你说，"Zero的核心，就在这张嘴里面。"

题目描述

给定一张图，判断它是否是平面图（可以画在平面上，边不相交）。如果是，输出一种平面嵌入方案。

输入格式

$n, m$。然后 $m$ 条边 $(u, v)$。

输出格式

如果是平面图，输出 "YES" 和每个点的坐标；否则输出 "NO"。

输入样例

3 2
1 2
2 3

输出样例

NO
NO
NO

提示

• Kuratowski定理：一个图是平面图当且仅当它不包含 $K_5$ 或 $K_{3,3}$ 的细分。
• 实用方法：尝试用平面嵌入算法（如LR方法）或DMP算法。
• 小数据可以用暴力搜索点的位置。

"图出来了。"你说。

"嘴在里面。"CC说。

"对。"你说，"但只有一个入口，太危险了。"

"那再找一个？"

"找不到了。"你说，"平面图只有一个外部面——入口只有一个。"

"那如果被封了呢？"

"那就完了。"你说，"所以我们需要——"

"退路。"CC说。

"对。"你说，"不止一条路。"

[第五题：预留退路]