<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
## 1. Abridged problem statement

We are given all facets of a convex polyhedron. Each facet is described by its vertices in cyclic order. Equal geometric vertices appear with exactly the same printed coordinates.

Build the edge graph of the polyhedron and find a Hamiltonian cycle in it: a cycle that visits every vertex exactly once and uses only polyhedron edges.

If such a cycle exists, print it as the sequence of vertex coordinates. Otherwise print `No`.

Constraints: at most 100 distinct vertices, 100 facets, 100 vertices per facet, coordinates printed with exactly 9 digits after the decimal point, sum of solid angles guaranteed less than `4` steradians.

---

## 2. Key observations

### Observation 1: Facets directly define the graph edges

For every facet, its vertices are given in boundary order. Therefore consecutive vertex pairs form polyhedron edges, and a set is used to deduplicate edges shared by two facets.

### Observation 2: Vertices can be identified by their printed coordinates

The statement guarantees that if the same point appears several times, its coordinates are printed exactly the same. The solution reads coordinates as strings and converts to integer nanounits (`llround(stod(s) * 1e9)`) for map-keyed deduplication. The original strings are kept for output.

### Observation 3: The solid angle condition guarantees Hamiltonicity

By Barnette's theorem, the total solid angle condition (less than `4` steradians) implies the edge graph of the convex polyhedron has a Hamiltonian cycle. So the answer is always `Yes` for valid inputs.

### Observation 4: Backtracking with Warnsdorff's heuristic and two pruning rules

With at most 100 vertices the graph is small. A DFS backtracking search starting from vertex 0 finds the cycle. At each step, try the unvisited neighbor with the fewest unvisited neighbors first (Warnsdorff's rule). Prune when:
- Any unvisited vertex has fewer than 2 usable neighbors (unvisited, current endpoint, or start).
- Not all unvisited vertices are reachable from the current endpoint through unvisited vertices.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n = 0;
vector<array<string, 3>> vertex_coord;
vector<vector<int>> adj;
vector<vector<char>> connected;
map<array<int64_t, 3>, int> vertex_id;
vector<char> visited;
vector<int> path;

void read() {
    int f;
    cin >> f;

    set<pair<int, int>> edges;
    for(int facet = 0; facet < f; facet++) {
        int k;
        cin >> k;

        vector<int> ids(k);
        for(int i = 0; i < k; i++) {
            array<string, 3> s;
            cin >> s[0] >> s[1] >> s[2];

            array<int64_t, 3> key;
            for(int j = 0; j < 3; j++) {
                key[j] = llround(stod(s[j]) * 1e9);
            }

            auto it = vertex_id.find(key);
            if(it == vertex_id.end()) {
                ids[i] = n++;
                vertex_id[key] = ids[i];
                vertex_coord.push_back(s);
            } else {
                ids[i] = it->second;
            }
        }

        for(int i = 0; i < k; i++) {
            int a = ids[i], b = ids[(i + 1) % k];
            if(a > b) {
                swap(a, b);
            }
            edges.insert({a, b});
        }
    }

    adj.assign(n, {});
    connected.assign(n, vector<char>(n, 0));
    for(auto& e: edges) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
        connected[e.first][e.second] = 1;
        connected[e.second][e.first] = 1;
    }
}

bool dfs(int cur, int depth) {
    if(depth == n) {
        return connected[cur][path[0]];
    }

    for(int u = 0; u < n; u++) {
        if(visited[u]) {
            continue;
        }

        int avail = 0;
        for(int nb: adj[u]) {
            if(!visited[nb] || nb == cur || nb == path[0]) {
                avail++;
            }
        }

        if(avail < 2) {
            return false;
        }
    }

    int target = n - depth;
    vector<char> seen(n, 0);
    vector<int> reach;
    for(int nb: adj[cur]) {
        if(!visited[nb] && !seen[nb]) {
            seen[nb] = 1;
            reach.push_back(nb);
        }
    }

    int cnt = reach.size();
    while(!reach.empty()) {
        int x = reach.back();
        reach.pop_back();
        for(int nb: adj[x]) {
            if(!visited[nb] && !seen[nb]) {
                seen[nb] = 1;
                cnt++;
                reach.push_back(nb);
            }
        }
    }

    if(cnt != target) {
        return false;
    }

    vector<pair<int, int>> cand;
    for(int nb: adj[cur]) {
        if(visited[nb]) {
            continue;
        }

        int deg = 0;
        for(int x: adj[nb]) {
            if(!visited[x]) {
                deg++;
            }
        }
        cand.push_back({deg, nb});
    }

    sort(cand.begin(), cand.end());
    for(auto& c: cand) {
        int nb = c.second;
        visited[nb] = 1;
        path[depth] = nb;
        if(dfs(nb, depth + 1)) {
            return true;
        }
        visited[nb] = 0;
    }

    return false;
}

void solve() {
    // Geometry to graph: the facets arrive as cyclic vertex lists, so the edge
    // graph is rebuilt by identifying vertices with equal coordinates (rounded
    // to the 9 printed digits, safe because distinct vertices lie at least
    // 5e-7 apart) and joining every facet's consecutive vertices; an edge that
    // borders two facets is simply encountered twice. By Steinitz's theorem
    // this graph is planar and 3-connected, i.e. a genuine polyhedral graph.
    //
    // The solid angle at a vertex is the area its incident faces carve out of a
    // unit sphere centred there. For a vertex of degree d it equals the
    // spherical-polygon excess (the sum of the dihedral angles around the
    // vertex) - (d - 2)*pi, and always lies strictly between 0 and 2*pi.
    // Summing this over all vertices gives S(P), the total solid angle, with a
    // full sphere measuring 4*pi steradians.
    //
    // Barnette's theorem ties S(P) to Hamiltonicity: a 3-polytope's
    // combinatorial type can be realised by polyhedra whose total solid angle
    // is arbitrarily close to 0 exactly when its edge graph has a Hamiltonian
    // cycle, while every non-Hamiltonian type keeps S(P) bounded away from 0.
    // The intuition for one direction is that a Hamiltonian cycle lets one
    // flatten the polyhedron towards that cycle, driving every vertex's solid
    // angle to 0, which no non-Hamiltonian type permits. The problem promises
    // S(P) < 4 steradians, which sits under that non-Hamiltonian bound, so the
    // graph is guaranteed Hamiltonian and the answer is always "Yes".
    // Grinberg's theorem gives a separate, purely combinatorial necessary
    // condition for planar Hamiltonicity but it is not needed here.
    //
    // Constructing the cycle is the only real work, and a guaranteed-polynomial
    // route exists in special cases: a 4-connected planar graph is Hamiltonian
    // and Chiba-Nishizeki finds a cycle in linear time. But small-solid-angle
    // polyhedra need not be 4-connected (a thin prism is only 3-connected), and
    // turning Barnette's "flatten towards the cycle" argument into a direct
    // construction is fiddly, so with at most 100 vertices we instead opt for a
    // heuristic search; the guaranteed existence of a cycle keeps it fast in
    // practice on these instances, though it carries no worst-case bound.
    //
    // The search is a backtracking walk from vertex 0. At each step it extends
    // the path to the unvisited neighbour that itself has the fewest unvisited
    // neighbours (Warnsdorff's rule), which heads into the cramped corners of
    // the graph first and so rarely has to backtrack. A branch is dropped the
    // moment it becomes unsatisfiable: some unvisited vertex is left with fewer
    // than two usable incident edges (it could never get both a predecessor and
    // a successor), or the unvisited vertices stop being reachable from the
    // current endpoint. The path closes into a cycle once all n vertices are
    // used and the final one is adjacent to vertex 0.
    //
    // Some references are:
    // - D. Barnette, "The sum of the solid angles of a d-polytope",
    //   Geometriae Dedicata 1 (1972), 100-102, doi:10.1007/BF00147383.
    // - E. Ja. Grinberg (1968), "Plane homogeneous graphs of degree three
    //   without Hamiltonian circuits"; English translation by D. Zeps,
    //   arXiv:0908.2563.

    visited.assign(n, 0);
    path.assign(n, 0);
    visited[0] = 1;
    path[0] = 0;

    if(dfs(0, 1)) {
        cout << "Yes\n" << n << "\n";
        for(int i = 0; i < n; i++) {
            auto& c = vertex_coord[path[i]];
            cout << c[0] << ' ' << c[1] << ' ' << c[2] << '\n';
        }
    } else {
        cout << "No\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution

```python
import sys
sys.setrecursionlimit(10000)


def solve():
    data = sys.stdin.read().split()
    ptr = 0

    f = int(data[ptr])
    ptr += 1

    vertex_id = {}
    vertex_coord = []
    edges = set()

    for _ in range(f):
        k = int(data[ptr])
        ptr += 1

        ids = []
        for _ in range(k):
            x = data[ptr]
            y = data[ptr + 1]
            z = data[ptr + 2]
            ptr += 3

            key = (x, y, z)
            if key not in vertex_id:
                vertex_id[key] = len(vertex_coord)
                vertex_coord.append(key)
            ids.append(vertex_id[key])

        for i in range(k):
            a = ids[i]
            b = ids[(i + 1) % k]
            if a > b:
                a, b = b, a
            edges.add((a, b))

    n = len(vertex_coord)

    adj = [[] for _ in range(n)]
    connected = [[False] * n for _ in range(n)]

    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
        connected[a][b] = True
        connected[b][a] = True

    visited = [False] * n
    path = [0] * n
    visited[0] = True
    path[0] = 0

    def dfs(cur, depth):
        if depth == n:
            return connected[cur][path[0]]

        for u in range(n):
            if visited[u]:
                continue
            avail = 0
            for nb in adj[u]:
                if (not visited[nb]) or nb == cur or nb == path[0]:
                    avail += 1
            if avail < 2:
                return False

        target = n - depth
        seen = [False] * n
        stack = []
        for nb in adj[cur]:
            if not visited[nb] and not seen[nb]:
                seen[nb] = True
                stack.append(nb)
        cnt = len(stack)
        while stack:
            x = stack.pop()
            for nb in adj[x]:
                if not visited[nb] and not seen[nb]:
                    seen[nb] = True
                    cnt += 1
                    stack.append(nb)
        if cnt != target:
            return False

        candidates = []
        for nb in adj[cur]:
            if visited[nb]:
                continue
            deg = 0
            for x in adj[nb]:
                if not visited[x]:
                    deg += 1
            candidates.append((deg, nb))
        candidates.sort()

        for _, nb in candidates:
            visited[nb] = True
            path[depth] = nb
            if dfs(nb, depth + 1):
                return True
            visited[nb] = False

        return False

    found = dfs(0, 1)

    out = []
    if found:
        out.append("Yes")
        out.append(str(n))
        for v in path:
            x, y, z = vertex_coord[v]
            out.append(f"{x} {y} {z}")
    else:
        out.append("No")

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()
```
