Untitled

#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstdio>

#include <queue>

#include <deque>

#include <bitset>

#include <set>

#include <unordered_set>

#include <map>

#include <unordered_map>

#include <random>

#include <ctime>

#include <utility>

#include <fstream>

 

#pragma GCC optimize("Ofast")

#pragma GCC optimize("no-stack-protector")

#pragma GCC optimize("unroll-loops")

#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")

#pragma GCC optimize("fast-math")

#pragma comment(linker, "/STACK:256000000")

#pragma warning(disable:4996)

 

using namespace std;

 

typedef long long ll;

typedef long double ld;

 

const char el = '\n';

const int inf = 1e9;

const ll llinf = 1e18, mod = 1000'000'007ll;

const ld pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825;

 

#define forn(i, n) for (int i = 0; i < (int)n; ++i)

#define firn(i, n) for (int i = 1; i < (int)n; ++i)

#define all(v) v.begin(), v.end()

#define x first

#define y second

 

template<typename T> bool uin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }

template<typename T> bool uax(T &a, T b) { if (b > a) { a = b; return 1; } return 0; }

template<class iterator> void output(iterator begin, iterator end, char p = ' ', ostream & out = cout) { while (begin != end) { out << (*begin) << p; begin++; } out << '\n'; }

template<class T> void output(T x, char p = ' ', ostream & out = cout) { output(all(x), p, out); }

 

mt19937 rnd(time(NULL));

 

vector<pair<int, int>> g[100000];

 

struct edge {

    int v, u;

    bool k;

};

 

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int n, m;

    cin >> n >> m;

    vector<int> r(n, 0);

    vector<edge> a(m);

    forn(i, m) {

        int v, u;

        cin >> v >> u;

        v--; u--;

        a[i] = { v, u, 1 };

        g[v].push_back({ u, i });

        g[u].push_back({ v, i });

    }

    vector<int> q, ans;

    q.push_back(0);

    while (!q.empty()) {

        int v = q.back();

        while (r[v] < (int)g[v].size() && !a[g[v][r[v]].y].k) r[v]++;

        if (r[v] < (int)g[v].size()) {

            q.push_back(g[v][r[v]].x);

            a[g[v][r[v]].y].k = 0;

            r[v]++;

        }

        else {

            ans.push_back(v + 1);

            q.pop_back();

        }

    }

    output(ans);

#ifdef _DEBUG

    system("pause");

#endif

    return 0;

}