#P18768. Homework Of Xenia

Homework Of Xenia

Homework Of Xenia

Xenia正在大学学习离散代数拓扑几何,但她缺了很多节课。作为惩罚,老师给她布置了下面的作业。

给定平面图 GG,请将它嵌入 Z10\mathbb Z^{10}:所有顶点对应的点必须两两不同,所有坐标的绝对值不超过 10610^6,每条边对应连接其两个端点的线段,且所有边的长度相等。嵌入后的线段允许相交。

帮助Xenia完成作业。

输入格式

第一行包含两个整数 n,mn,m,分别表示顶点数和边数:

1≤n≤1000,0≤m≤n(n−1)2.1\le n\le1000,\qquad 0\le m\le\frac{n(n-1)}2.

接下来 mm 行,每行两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n),表示一条无向边。

保证输入图是平面图,没有自环和重边。

输出格式

如果无法嵌入,输出一个整数 −1-1。

否则输出 nn 行,第 ii 行给出对应顶点的10个整数坐标 ci,1,…,ci,10c_{i,1},\ldots,c_{i,10},满足 ∣ci,j∣≤106|c_{i,j}|\le10^6,并且所有顶点的坐标向量两两不同。

必须存在同一个正数 dd,使得输入中每条边 (u,v)(u,v) 都满足

$$\operatorname{dist}(c_u,c_v)=d,\qquad \operatorname{dist}(c_u,c_v)=\sqrt{\sum_{j=1}^{10}(c_{u,j}-c_{v,j})^2}.$$

不同连通分量的边也必须共用同一个 dd。没有边的顶点对不受距离条件限制;当 m=0m=0 时,只需满足坐标范围和顶点两两不同。答案可能不唯一,输出任意合法方案。

样例

样例1

输入:

2 1
1 2

输出(其中一种合法方案):

0 0 0 0 0 0 0 0 0 0
0 5 7 0 1 7 9 0 2 0

样例2

输入:

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

输出(其中一种合法方案):

0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0