hamilton.cpp

#include<iostream>
#include<cstdlib>
#include<vector>
#include<climits>

#define long long long
#define nln '\n'

const long I = LLONG_MAX;

using namespace std;

vector<vector<bool>> mtx;
long n;
vector<bool> pic;
vector<long> pat, res;
bool ok = 0;

void dfs(long i, long cnt)
{
    if (ok)
        return;
    if (cnt == n){
        if (!mtx[i][1])
            return;
        res = pat;
        ok = 1;
        return;
    }
    for (long j = 1; j <= n; ++j)
        if (mtx[i][j] && !pic[j]){
            pic[j] = 1;
            pat.push_back(j);
            dfs(j, cnt+1);
            pat.pop_back();
            pic[j] = 0;
        }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    //freopen("hamilton.inp", "r", stdin);
    long m;
    cin >> n >> m;
    mtx.resize(n+1);
    for (long i = 0; i <= n; ++i)
        mtx[i].resize(n+1, 0);
    while (m--){
        long x, y;
        cin >> x >> y;
        mtx[x][y] = 1;
        mtx[y][x] = 1;
    }

    pic.resize(n+1, 0);
    pic[1] = 1;
    dfs(1, 1);
    cout << 1 << ' ';
    for (const auto &i : res)
        cout << i << ' ';
    cout << 1 << nln;
    cout << nln;
    return 0;
}