题目描述

如果一个无向图可以把每个顶点映射到平面上的一个点，并且满足：

• 有边相连的两个顶点对应点之间的距离恰好为 $1$；
• 没有边相连的两个不同顶点对应点之间的距离不等于 $1$；

那么称这个图为 unit-distance graph。

给定一个无向简单图，判断它是否是 unit-distance graph。如果是，请构造对应的平面点集。

输入格式

第一行两个整数 $n,m$：

$1\le n\le7$，

其中 $n$ 为顶点数，$m$ 为边数。

接下来 $m$ 行，每行两个不同的整数 $u,v$，表示一条无向边。顶点编号为 $0,1,\dots,n-1$。

保证无重边。

输出格式

如果不存在满足要求的点集，输出：

No

否则输出：

Yes
x0 y0
x1 y1
...
x(n-1) y(n-1)

坐标的绝对值不得超过 $100$。

评测时使用以下误差规则：

• 任意两个点之间的距离至少为 $10^{-2}$；
• 如果 $u,v$ 有边，则其距离与 $1$ 的误差不超过 $10^{-7}$；
• 如果 $u,v$ 没有边，则其距离与 $1$ 的差至少为 $10^{-2}$。

样例 1

4 6
0 1
0 2
0 3
1 2
1 3
2 3

No

样例 2

5 6
0 1
1 2
2 3
3 0
3 4
4 0

一种合法输出为：

Yes
0.0 0.0
1.0 0.0
1.0 1.0
0.0 1.0
-0.8660254037844386 0.5

本题构造答案不唯一，题包使用 SPJ。