p122.ans1
======================
1 3 4 2 1

=================
p122.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;
}

=================
p122.in1
======================
4
2 3
1 4
1 4
2 3

=================
statement.txt
======================
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

=================
