<|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  
- Dirac’s 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 in a Dirac graph. It maintains a current cycle and repeatedly either extends it by one new vertex or, when stuck, “rotates” part of the cycle to make room for a new vertex.

3. Full Solution Approach  

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

We will 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 cycle. 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 that is already in our cycle at position j = pos[w], mark the vertex cycle[j+1] (the successor of w in the cycle), if j+1 exists.  
     3. Now scan unvisited vertices x (pos[x]==–1). For each such x, look at its neighbors y: if marked[y] is true, then we can “rotate” at y:  
        • Let j = pos[y]. Reverse the segment cycle[j+1 … end] in the cycle.  
        • After reversal, update pos[] for every vertex in that reversed segment to its new index.  
        • Finally set pos[x]=i and append x to cycle.  
     This rotation reconnects edges so that u now has at least one unvisited neighbor to add (namely x), and we continue.  

After we have inserted all N vertices, cycle has length N. We output cycle (converted to 1-based) followed by cycle[0] again to close the loop.  

Because of Dirac’s condition, step B always succeeds; we never have to print “No solution” for N≥3. For N=2 you can handle it separately (if 2 are mutual friends, the cycle is “1 2 1”).

4. C++ Implementation with Detailed Comments  

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

// Solve the book-passing problem via rotation-based Hamiltonian construction
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;

    // Read adjacency lists (convert to 0-based)
    vector<vector<int>> adj(N);
    cin.ignore();  // consume end of line
    for (int i = 0; i < N; i++) {
        string line;
        getline(cin, line);
        istringstream ss(line);
        int f;
        while (ss >> f) {
            adj[i].push_back(f - 1);
        }
    }

    // Special case N=2
    if (N == 2) {
        // Check mutual friendship
        if ((find(adj[0].begin(), adj[0].end(), 1) != adj[0].end()) &&
            (find(adj[1].begin(), adj[1].end(), 0) != adj[1].end())) {
            cout << "1 2 1\n";
        } else {
            cout << "No solution\n";
        }
        return 0;
    }

    // pos[v] = index of v in 'cycle', or -1 if not yet inserted
    vector<int> pos(N, -1);

    // cycle = current path/cycle under construction, start at 0
    vector<int> cycle;
    cycle.push_back(0);
    pos[0] = 0;

    // Insert vertices one by one at times i=1..N-1
    for (int time = 1; time < N; time++) {
        int u = cycle.back();
        bool extended = false;

        // A. Try to directly extend by an unvisited neighbor
        for (int v : adj[u]) {
            if (pos[v] == -1) {
                pos[v] = time;
                cycle.push_back(v);
                extended = true;
                break;
            }
        }
        if (extended) continue;

        // B. Rotation step: mark successors of visited neighbors of u
        vector<char> marked(N, 0);
        for (int w : adj[u]) {
            int j = pos[w];
            if (j >= 0 && j + 1 < (int)cycle.size()) {
                marked[ cycle[j+1] ] = 1;
            }
        }

        // Find an unvisited x that has a marked neighbor y
        bool done = false;
        for (int x = 0; x < N && !done; x++) {
            if (pos[x] != -1) continue;
            for (int y : adj[x]) {
                if (marked[y]) {
                    // We will rotate after position pos[y]
                    int j = pos[y];
                    // Reverse the tail cycle[j+1..end]
                    reverse(cycle.begin() + j + 1, cycle.end());
                    // Update pos[] for affected vertices
                    for (int k = j+1; k < (int)cycle.size(); k++) {
                        pos[ cycle[k] ] = k;
                    }
                    // Finally append x
                    pos[x] = time;
                    cycle.push_back(x);
                    done = true;
                    break;
                }
            }
        }
        // By Dirac's theorem this always finds something
    }

    // Output the cycle in 1-based form, then return to 1
    for (int v : cycle) {
        cout << (v+1) << ' ';
    }
    cout << (cycle[0]+1) << "\n";
    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)

    # Special case N=2
    if N == 2:
        if 1 in adj[0] and 0 in adj[1]:
            print("1 2 1")
        else:
            print("No solution")
        return

    # pos[v] = insertion index of v in 'cycle', or -1 if not inserted 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 visited neighbor of u
        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 after position pos[y]
                    j = pos[y]
                    # Reverse the tail
                    tail = list(reversed(cycle[j+1:]))
                    cycle = cycle[:j+1] + tail
                    # Update pos[] for reversed segment
                    for k in range(j+1, len(cycle)):
                        pos[cycle[k]] = k
                    # Append x
                    pos[x] = time
                    cycle.append(x)
                    found = True
                    break
            if found:
                break
        # By Dirac’s condition this must succeed

    # 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 visited neighbor w of u and mark w’s successor in the cycle. Any unvisited vertex x adjacent to one of these marked successors y can be spliced into the cycle by reversing the segment after y.  
- This “rotation” restores the ability to extend and, thanks to the high minimum degree, never fails.