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

122. The book

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


There is a group of N (2<=N<=1000) people which are numbered 1 through N, and everyone of them has not less than [ (N+1) / 2 ] friends. A man with number 1 has the book, which others want to read. Write the program which finds a way of transferring the book so that it will visit every man only once, passing from the friend to the friend, and, at last, has come back to the owner. Note: if A is a friend of B then B is a friend of A.


Input

First line of input contains number N. Next N lines contain information about friendships. (i+1)-th line of input contains a list of friends of i-th man.


Output

If there is no solution then your program must output 'No solution'.   Else your program must output exactly N+1 number: this sequence should begin and should come to end by number 1, any two neighbours in it should be friends, and any two elements in it, except for the first and last, should not repeat.


Sample Input

4
2 3
1 4
1 4
2 3
Sample Output

1 3 4 2 1

<|response|>
1. Abridged Problem Statement
You are given an undirected graph of N people (nodes numbered 1…N) where each person has at least ⌈(N+1)/2⌉ friends (edges). Person 1 starts with a book and wants to pass it friend-to-friend so that every person reads it exactly once, and finally it returns to person 1. Find such a Hamiltonian cycle or report “No solution.”

2. Key Observations
- The Dirac/Ore theorem guarantees that any graph on N ≥ 3 vertices with minimum degree ≥ N/2 has a Hamiltonian cycle. Here the minimum degree bound ⌈(N+1)/2⌉ is at least N/2, so a cycle must exist.
- A constructive O(N³)-time “rotation” (or “insertion”) method can build one Hamiltonian cycle. It maintains a current path and repeatedly either extends it by one new vertex or, when stuck, “rotates” part of the path to make room for a new vertex.

3. Full Solution Approach

Work in 0-based indices (person 1 → vertex 0). We maintain:
  • cycle: a list of vertices in the current path, initially [0].
  • pos[v]: the position (index) of v in cycle, or –1 if v is not yet placed.

Insert the remaining N−1 vertices one by one, at times i = 1…N−1:
  A. Extension step
     Let u = cycle.back() be the current end of the path. Try to find any neighbor v of u with pos[v]==–1 (unvisited).
     If found, set pos[v]=i, append v to cycle, and proceed to the next i.
  B. Rotation step (when u has no unvisited neighbor)
     1. Build a boolean array marked[] of size N.
     2. For each neighbor w of u (all already on the path at position pos[w]), mark cycle[pos[w]+1], the successor of w.
     3. Scan unvisited vertices new_v (pos[new_v]==–1). For each, look at its neighbors y: if marked[y] is true, then we can “rotate” at y:
        • Reverse the suffix of the path starting at position pos[y] (cycle[pos[y] .. end]).
        • This reversal turns the predecessor of y into the new path endpoint, which is adjacent to new_v.
        • Set pos[new_v]=i and append new_v to cycle.
     This rotation re-exposes an endpoint that can be extended, and we continue.

After all N vertices are placed, cycle has length N. Output cycle (converted to 1-based) followed by cycle[0] again to close the loop. Because of the minimum-degree condition, step B always succeeds for N≥3.

4. C++ Implementation
```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;
vector<vector<int>> adj;

void read() {
    cin >> n;
    adj.assign(n, {});
    cin.ignore();
    for(int i = 0; i < n; i++) {
        string line;
        getline(cin, line);

        istringstream ss(line);
        int neighbor;
        while(ss >> neighbor) {
            adj[i].push_back(neighbor - 1);
        }
    }
}

void solve() {
    // Each person has at least ceil(N/2) friends, so by Ore's theorem a
    // Hamiltonian cycle exists; this builds one by the classic constructive
    // proof. We grow a simple path starting at vertex 0, tracking pos[v] = the
    // position of v on the path. At each step, if the path's last vertex has an
    // unvisited neighbour we extend to it. Otherwise we find an unvisited
    // vertex new_v adjacent to some vertex marked[v] (where a vertex is marked
    // if it immediately follows a neighbour of the current endpoint on the
    // path); reversing the path suffix after that neighbour exposes a new
    // endpoint adjacent to new_v, letting us attach it. After N steps the path
    // is Hamiltonian and is closed back to vertex 1.

    vector<int> pos(n, -1);
    vector<int> cycle = {0};
    pos[0] = 0;

    for(int i = 1; i < n; i++) {
        bool found = false;
        int u = cycle.back();
        for(int v: adj[u]) {
            if(pos[v] == -1) {
                pos[v] = i;
                cycle.push_back(v);
                found = true;
                break;
            }
        }

        if(found) {
            continue;
        }

        vector<bool> marked(n, false);
        for(int v: adj[u]) {
            marked[cycle[pos[v] + 1]] = true;
        }

        for(int new_v = 0; new_v < n; new_v++) {
            if(pos[new_v] == -1) {
                bool found = false;
                for(int v: adj[new_v]) {
                    if(marked[v]) {
                        found = true;
                        reverse(cycle.begin() + pos[v], cycle.end());
                        break;
                    }
                }

                if(found) {
                    pos[new_v] = i;
                    cycle.push_back(new_v);
                    break;
                }
            }
        }
    }

    for(int i = 0; i < n; i++) {
        cout << cycle[i] + 1 << ' ';
    }
    cout << cycle[0] + 1;
    cout << '\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        return
    N = int(data[0])
    # Build adjacency lists in 0-based indexing
    adj = []
    for i in range(1, N+1):
        if data[i].strip():
            nbrs = [int(x)-1 for x in data[i].split()]
        else:
            nbrs = []
        adj.append(nbrs)

    # pos[v] = position of v in 'cycle', or -1 if not placed yet
    pos = [-1]*N
    cycle = [0]
    pos[0] = 0

    # Insert the other N-1 vertices
    for time in range(1, N):
        u = cycle[-1]
        extended = False

        # A. Try to extend directly
        for v in adj[u]:
            if pos[v] == -1:
                pos[v] = time
                cycle.append(v)
                extended = True
                break
        if extended:
            continue

        # B. Rotation step
        marked = [False]*N
        # Mark successors of each neighbor of u on the path
        for w in adj[u]:
            j = pos[w]
            if j != -1 and j+1 < len(cycle):
                marked[cycle[j+1]] = True

        # Find an unvisited x with a marked neighbor y
        found = False
        for x in range(N):
            if pos[x] != -1:
                continue
            for y in adj[x]:
                if marked[y]:
                    # Rotate the suffix from position pos[y]
                    j = pos[y]
                    tail = list(reversed(cycle[j:]))
                    cycle = cycle[:j] + tail
                    # Update pos[] for reversed segment
                    for k in range(j, len(cycle)):
                        pos[cycle[k]] = k
                    # Append x
                    pos[x] = time
                    cycle.append(x)
                    found = True
                    break
            if found:
                break

    # Output the result in 1-based form, closing the cycle
    result = [v+1 for v in cycle] + [cycle[0]+1]
    print(" ".join(map(str, result)))

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

Explanation of key steps:
- We greedily add unvisited neighbors whenever possible.
- When stuck at u, we look at each neighbor w of u and mark w’s successor on the path. Any unvisited vertex x adjacent to one of these marked successors y can be spliced into the path by reversing the suffix from y’s position.
- This “rotation” restores the ability to extend and, thanks to the high minimum degree, never fails.
