427. Hamiltonian polyhedron

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



You are given a convex polyhedron with the sum of its solid angles less than 4 (in steradians; the full angle is in this case equal to 4pi). Find out whether there exists a cycle that passes through all vertices of the polyhedron exactly once. The cycle must have edges of the polyhedron as its edges, and no edge can be used more than once in the cycle. You can leave some of the edges of the polyhedron unused.

Input
The first line of the input file contains one integer number f — the number of facets of the polyhedron. Then all f facets are described. Each description begins with a line with single integer k — the number of vertices of the facet. The next k lines contain 3 real numbers each — the vertex coordinates. The points are given in the order they appear on the border of the facet (either clockwise or counter-clockwise). The numbers are given with exactly 9 digits after the decimal point. If a point is listed in several facet descriptions, its coordinates in all descriptions will be exactly the same.

The overall number of vertices of the polyhedron will be at most 100. The overall number of facets and the number of vertices on any facet will be at most 100 as well.

The coordinates of the points are not the exact coordinates in 3-dimensional space, they are rounded to 9 digits after the decimal point from their true value. Some of the points can be very close, but the distance between any two different points is at least 5 · 10-7. The absolute values of the coordinates of the points do not exceed 1000.

Output
If there is no such cycle as described in the problem statement, output "
No
" on the first line of the output file, otherwise output "
Yes
". In the latter case, output the description of the cycle: on the second line output n — the number of vertices of the polyhedron; on the next n lines output the coordinates of the vertices in the order they appear along the cycle, exactly as they were given in the input file, with the same 9 digits after the decimal point.

Example(s)
sample input
sample output
4
3
100.146488845 0.000000000 0.000000000 
100.145878719 0.349576483 0.000000000 
-100.145878719 -0.349576483 0.000000000 
3
33.382162948 0.000000000 1.219611194 
100.146488845 0.000000000 0.000000000 
100.145878719 0.349576483 0.000000000 
3
33.382162948 0.000000000 1.219611194 
100.145878719 0.349576483 0.000000000 
-100.145878719 -0.349576483 0.000000000 
3
33.382162948 0.000000000 1.219611194 
-100.145878719 -0.349576483 0.000000000 
100.146488845 0.000000000 0.000000000 
Yes
4
-100.145878719 -0.349576483 0.000000000 
33.382162948 0.000000000 1.219611194 
100.146488845 0.000000000 0.000000000 
100.145878719 0.349576483 0.000000000 




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