p156.ans1
======================
1 2 3 4

=================
p156.ans2
======================
-1

=================
p156.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, m;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> next_node, hcycle;

void add_edge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int match_nodes(int u, int root) {
    int ans = 1;
    visited[u] = true;
    for(int v: adj[u]) {
        if(adj[v].size() == 2) {
            next_node[u] = v;
        } else if(adj[v].size() > 2 && !visited[v]) {
            ans += match_nodes(v, root);
        }
    }
    return ans;
}

void dfs(int u, bool in_path) {
    visited[u] = true;
    if(adj[u].size() > 2 && !visited[next_node[u]]) {
        dfs(next_node[u], false);
    }
    for(int v: adj[u]) {
        if(!visited[v]) {
            if(adj[u].size() == 2) {
                dfs(v, false);
            } else if(!in_path && adj[v].size() > 2) {
                dfs(v, true);
            }
        }
    }
    hcycle.push_back(u);
}

void read() {
    cin >> n >> m;
    adj.assign(n, {});
    visited.assign(n, false);
    next_node.assign(n, -1);

    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        add_edge(u, v);
    }
}

void solve() {
    // The strange-graph conditions force a rigid structure: every high-degree
    // vertex (deg > 2) has a unique degree-2 neighbour that must be used to
    // exit it on the cycle, and high-degree vertices come in even-sized
    // clusters (cliques connected through degree-2 bridges). next_node[u]
    // records, for each high-degree u, the forced degree-2 neighbour. We first
    // verify every cluster of adjacent high-degree vertices has even size
    // (otherwise no Hamiltonian cycle exists), then run a single DFS that
    // walks the forced edges to lay out the cycle in hcycle. If the walk does
    // not visit all n vertices, no cycle exists.

    for(int i = 0; i < n; i++) {
        if(adj[i].size() > 2 && !visited[i]) {
            if(match_nodes(i, i) & 1) {
                cout << "-1\n";
                return;
            }
        }
    }

    fill(visited.begin(), visited.end(), false);
    hcycle.clear();
    dfs(0, false);

    if((int)hcycle.size() != n) {
        cout << "-1\n";
    } else {
        reverse(hcycle.begin(), hcycle.end());
        for(int u: hcycle) {
            cout << u + 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();
        solve();
    }

    return 0;
}

=================
p156.in1
======================
4 4
1 2 2 3 3 4 4 1

=================
p156.in2
======================
9 12
1 2 2 3 3 1 1 4 2 5 3 6
4 7 5 8 6 9 7 8 8 9 9 7

=================
statement.txt
======================
156. Strange Graph
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard input
output: standard output



Let us consider an undirected graph G = <V, E>. We say that two vertices u and v are neighbours if (u, v) in E. In this case we also say that u is a neighbour of v and v is a neighbour of u. Let us denote by N(v) the set of neighbours of v. Recall that the number of neighbours of v is called the degree of this vertex and is denoted by deg v.
We call graph G strange if it is connected and for its every vertex v the following conditions are satisfied:
  1. deg v >= 2 (i.e. there are at least two neighbours of v)
  2. if deg v = 2 then the two neighbours of v are not connected by an edge
  3. if deg v > 2 then there exists u in N(v), such that the following is true:
    (a) deg u = 2
    (b) any two diRerent vertices w1, w2 in N(v) \ {u} are neighbours, i.e. (w1,w2) in E
You are given some strange graph G. Find a hamiltonian cycle in it, i.e. a cycle that goes through every vertex of G exactly once.

Input
The first line of the input file contains two integer numbers N and M - the number of vertices and edges in G respectively (3 <= N <= 10000, M <= 100000). 2M integer numbers follow - each pair represents vertices connected by the corresponding edge (vertices are numbered from 1 to N). It is guaranteed that each edge occurs exactly once in the input file and that there are no loops (i.e. ends of each edge are distinct).

Output
If there is no hamiltonian cycle in G, print -1 in the first line of the output file. In the other case output N numbers - the sequence of vertices of G as they appear in the hamiltonian cycle found (note that the last vertex must be connected to the first one). If there are several solutions, output any one.

Sample test(s)

Input
Sample input #1
4 4
1 2 2 3 3 4 4 1

Sample input #2
9 12
1 2 2 3 3 1 1 4 2 5 3 6
4 7 5 8 6 9 7 8 8 9 9 7

Output
Sample output #1
1 2 3 4

Sample output #2
-1

Note
Author:	Andrew Stankevich
Resource:	ACM ICPC 2002-2003 NEERC, Northern Subregion
Date:	November, 2002

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