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() {
    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;
                        int j = pos[v];
                        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;
}

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

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