430. Unit-distance graph

Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

A graph is called unit-distance graph when it's possible to map its vertices to points on a plane in such a way that the distance between the points that correspond to vertices that are connected by an edge is exactly 1, and the distance between the points that correspond to vertices that are not connected by an edge is not equal to 1 (but still greater than 0).

Given a graph, find out whether it's a unit-distance graph, and if yes, output the corresponding points on the plane.

The first line of the input file contains two integers n and m — the number of vertices and edges of the graph (1 ≤ n ≤ 7). The next m lines contain two distinct integers each, describing two vertices connected by an edge (the vertices are numbered starting from 0). Every two vertices can be connected by at most one edge.

If the graph is unit-distance, print "Yes" (without quotes) on the first line of output file, otherwise print "No" (without quotes). In the former case, then print n lines, each containing two floating-point numbers not exceeding 100 by absolute value — the coordinates of the corresponding points in the order the vertices are numbered. Your solution will be considered correct if no two points are closer than 10-2, the distance between points corresponding to connected vertices differs from 1 by no more than 10-7, and the distance between two points corresponding to non-connected vertices differs from 1 by at least 10-2.
sample input
sample output
4 6
0 1
0 2
0 3
2 1
3 1
2 3

sample input
sample output
5 6
0 1
1 2
2 3
3 0
3 4
4 0
0.0 0.0
1.0 0.0
1.0 1.0
0.0 1.0
-0.8660254037844386 0.5

Online Contester Team © 2002 - 2010. All rights reserved.