<|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:

- Number of distinct vertices ≤ `100`
- Number of facets ≤ `100`
- Vertices per facet ≤ `100`
- Coordinates are printed with exactly `9` digits after the decimal point
- The sum of solid angles is guaranteed to be less than `4`

---

## 2. Key observations needed to solve the problem

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

For every facet, its vertices are given in boundary order.

Therefore, if a facet contains vertices:

```text
v0, v1, v2, ..., vk-1
```

then the graph contains edges:

```text
(v0, v1), (v1, v2), ..., (vk-2, vk-1), (vk-1, v0)
```

The same edge may appear in two facet descriptions, so we should store edges in a set.

---

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

The statement says that if the same point appears several times, its coordinates are printed exactly the same.

So we can use the coordinate triple as a key:

```cpp
(x_string, y_string, z_string)
```

This also preserves the exact formatting needed for output.

---

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

The condition about the sum of solid angles being less than `4` steradians is a strong geometric promise.

A theorem by Barnette implies that, under this condition, the edge graph of the convex polyhedron is Hamiltonian.

So in valid official tests, a Hamiltonian cycle should exist. Still, our program can search for one and output `No` if the search fails.

---

### Observation 4: Backtracking is feasible with good pruning

A general Hamiltonian cycle problem is NP-hard, but here:

- `n ≤ 100`
- the graph is a special polyhedral graph
- a solution is promised to exist
- strong pruning makes the search practical

We build a Hamiltonian path starting from vertex `0`.

At each step, we extend the current path endpoint to one unvisited neighbor.

When all vertices are used, we only need to check whether the last vertex is adjacent to the start.

---

### Observation 5: Useful pruning rules

Suppose the current path is:

```text
start -> ... -> cur
```

For an unvisited vertex `u`, in the final Hamiltonian cycle it still needs two cycle-neighbors.

The only vertices it may still connect to are:

- other unvisited vertices
- the current endpoint `cur`
- the start vertex, to close the cycle

It cannot connect to an already visited internal path vertex.

So if an unvisited vertex has fewer than two such available neighbors, this branch is impossible.

Also, all remaining unvisited vertices must be reachable from `cur` through unvisited vertices. Otherwise the path cannot visit all of them.

---

## 3. Full solution approach based on the observations

### Step 1: Read input and build vertex IDs

Maintain:

```cpp
map<array<string, 3>, int> id;
vector<array<string, 3>> coord;
```

For every coordinate triple:

- if it was already seen, reuse its ID
- otherwise assign a new ID and store the original strings

---

### Step 2: Build the graph

For every facet:

1. Read all its vertex IDs into an array.
2. Add edges between consecutive IDs.
3. Also add the edge between the last and first vertex.

Use a set of normalized pairs:

```cpp
(min(a, b), max(a, b))
```

to avoid duplicate edges.

Then build:

- adjacency list `adj`
- adjacency matrix `connected`

The adjacency matrix allows `O(1)` checks when testing whether the Hamiltonian path closes into a cycle.

---

### Step 3: Backtracking search

We fix the first vertex as `0`.

Maintain:

```cpp
visited[v]  // whether vertex v is already in the current path
path[i]     // i-th vertex in the current path
```

Recursive state:

```cpp
dfs(cur, depth)
```

where:

- `cur` is the current endpoint
- `depth` is the number of vertices already in the path

If `depth == n`, return true only if:

```cpp
connected[cur][path[0]]
```

---

### Step 4: Prune impossible branches

Before trying extensions:

#### Pruning 1: each unvisited vertex needs at least 2 possible neighbors

For each unvisited vertex `u`, count neighbors `v` such that:

```cpp
!visited[v] || v == cur || v == path[0]
```

If this count is less than `2`, stop this branch.

#### Pruning 2: remaining vertices must be reachable

Start a DFS/BFS from all unvisited neighbors of `cur`, moving only through unvisited vertices.

If not all unvisited vertices are reached, stop this branch.

---

### Step 5: Choose next vertices in a good order

For every unvisited neighbor `v` of `cur`, compute how many unvisited neighbors it has.

Try vertices with smaller counts first.

This is similar to Warnsdorff’s heuristic and often greatly reduces backtracking.

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

int n; // number of distinct vertices

// Original printed coordinates of each vertex.
// Needed because output must match the input formatting exactly.
vector<array<string, 3>> coord;

// Graph representation.
vector<vector<int>> adj;

// connected[u][v] is true if there is an edge u-v.
// Used for fast cycle-closing check.
vector<vector<char>> connected;

// Backtracking state.
vector<char> visited;
vector<int> path;

bool dfs(int cur, int depth) {
    // If all vertices are already in the path,
    // the path is a Hamiltonian cycle only if the last vertex
    // is connected to the first one.
    if (depth == n) {
        return connected[cur][path[0]];
    }

    /*
        Pruning rule 1.

        Every unvisited vertex must still be able to get two neighbors
        in the final Hamiltonian cycle.

        It may connect to:
        - another unvisited vertex,
        - the current endpoint cur,
        - the start vertex path[0].

        It may not connect to an already visited internal path vertex.
    */
    for (int u = 0; u < n; u++) {
        if (visited[u]) continue;

        int available = 0;

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

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

    /*
        Pruning rule 2.

        All unvisited vertices must be reachable from cur
        through unvisited vertices. Otherwise the current path
        can never visit all remaining vertices.
    */
    int remaining = n - depth;

    vector<char> seen(n, 0);
    vector<int> stack;

    // Start from all unvisited neighbors of cur.
    for (int v : adj[cur]) {
        if (!visited[v] && !seen[v]) {
            seen[v] = 1;
            stack.push_back(v);
        }
    }

    int reached = (int)stack.size();

    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();

        for (int v : adj[u]) {
            if (!visited[v] && !seen[v]) {
                seen[v] = 1;
                reached++;
                stack.push_back(v);
            }
        }
    }

    if (reached != remaining) {
        return false;
    }

    /*
        Build candidate next vertices.

        We try more constrained vertices first:
        a vertex with fewer unvisited neighbors is tried earlier.
    */
    vector<pair<int, int>> candidates;

    for (int v : adj[cur]) {
        if (visited[v]) continue;

        int unvisitedDegree = 0;

        for (int to : adj[v]) {
            if (!visited[to]) {
                unvisitedDegree++;
            }
        }

        candidates.push_back({unvisitedDegree, v});
    }

    sort(candidates.begin(), candidates.end());

    // Try every possible next vertex.
    for (auto [_, nxt] : candidates) {
        visited[nxt] = 1;
        path[depth] = nxt;

        if (dfs(nxt, depth + 1)) {
            return true;
        }

        visited[nxt] = 0;
    }

    return false;
}

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

    int f;
    cin >> f;

    // Coordinate triple -> vertex id.
    map<array<string, 3>, int> vertexId;

    // Store unique undirected edges.
    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> p;
            cin >> p[0] >> p[1] >> p[2];

            if (!vertexId.count(p)) {
                int newId = (int)coord.size();
                vertexId[p] = newId;
                coord.push_back(p);
            }

            ids[i] = vertexId[p];
        }

        // Add all boundary edges of this facet.
        for (int i = 0; i < k; i++) {
            int a = ids[i];
            int b = ids[(i + 1) % k];

            if (a > b) swap(a, b);

            edges.insert({a, b});
        }
    }

    n = (int)coord.size();

    adj.assign(n, {});
    connected.assign(n, vector<char>(n, 0));

    for (auto [a, b] : edges) {
        adj[a].push_back(b);
        adj[b].push_back(a);

        connected[a][b] = 1;
        connected[b][a] = 1;
    }

    if (n < 3) {
        cout << "No\n";
        return 0;
    }

    visited.assign(n, 0);
    path.assign(n, 0);

    // Fix vertex 0 as the start of the cycle.
    visited[0] = 1;
    path[0] = 0;

    if (dfs(0, 1)) {
        cout << "Yes\n";
        cout << n << '\n';

        for (int i = 0; i < n; i++) {
            auto &p = coord[path[i]];
            cout << p[0] << ' ' << p[1] << ' ' << p[2] << '\n';
        }
    } else {
        cout << "No\n";
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys

sys.setrecursionlimit(10000)


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

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

    # Coordinate triple -> vertex id.
    vertex_id = {}

    # Original coordinates by vertex id.
    coord = []

    # Unique undirected edges.
    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

            p = (x, y, z)

            if p not in vertex_id:
                vertex_id[p] = len(coord)
                coord.append(p)

            ids.append(vertex_id[p])

        # Consecutive vertices of a facet form polyhedron edges.
        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(coord)

    if n < 3:
        print("No")
        return

    # Build graph.
    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

    # Start from vertex 0.
    visited[0] = True
    path[0] = 0

    def dfs(cur, depth):
        """
        Try to extend the current Hamiltonian path.

        cur:
            current endpoint of the path

        depth:
            number of vertices currently included in the path
        """

        # All vertices are used.
        # Check if the last vertex connects back to the first one.
        if depth == n:
            return connected[cur][path[0]]

        # Pruning rule 1:
        # Every unvisited vertex must still have at least two possible
        # neighbors in the final Hamiltonian cycle.
        for u in range(n):
            if visited[u]:
                continue

            available = 0

            for v in adj[u]:
                if (not visited[v]) or v == cur or v == path[0]:
                    available += 1

            if available < 2:
                return False

        # Pruning rule 2:
        # All unvisited vertices must be reachable from cur through
        # unvisited vertices.
        remaining = n - depth

        seen = [False] * n
        stack = []

        # Start from unvisited neighbors of cur.
        for v in adj[cur]:
            if not visited[v] and not seen[v]:
                seen[v] = True
                stack.append(v)

        reached = len(stack)

        while stack:
            u = stack.pop()

            for v in adj[u]:
                if not visited[v] and not seen[v]:
                    seen[v] = True
                    reached += 1
                    stack.append(v)

        if reached != remaining:
            return False

        # Candidate next vertices.
        # Store pairs (number_of_unvisited_neighbors, vertex).
        candidates = []

        for v in adj[cur]:
            if visited[v]:
                continue

            unvisited_degree = 0

            for to in adj[v]:
                if not visited[to]:
                    unvisited_degree += 1

            candidates.append((unvisited_degree, v))

        # Try the most constrained vertices first.
        candidates.sort()

        for _, nxt in candidates:
            visited[nxt] = True
            path[depth] = nxt

            if dfs(nxt, depth + 1):
                return True

            visited[nxt] = False

        return False

    found = dfs(0, 1)

    if not found:
        print("No")
        return

    out = []
    out.append("Yes")
    out.append(str(n))

    for v in path:
        x, y, z = coord[v]
        out.append(f"{x} {y} {z}")

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


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