Graph Ordering

input/code.cpp: In function 'void solve(int)':
input/code.cpp:65:9: warning: unused variable 'c' [-Wunused-variable]
     int c = 0, c2 = 0, c3 = ++cnt;
         ^
input/code.cpp:65:16: warning: unused variable 'c2' [-Wunused-variable]
     int c = 0, c2 = 0, c3 = ++cnt;
                ^~
input/code.cpp: In function 'int main()':
input/code.cpp:154:23: warning: unused variable 'pre' [-Wunused-variable]
         int ind = -1, pre = -1;
                       ^~~
input/code.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
input/code.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
int low[MAXN], disc[MAXN];
int vis[MAXN], t = 1, ap[MAXN];
vi adj[MAXN];
vector<vi> comps;
deque<int> st;

void dfs(int u, int p) {
    vis[u] = 1;
    disc[u] = low[u] = t++;
    int children = 0;
    st.pb(u);
    for (int v: adj[u]) {
        if (!vis[v]) {
            children++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if ((p != -1 && disc[u] <= low[v]) || (p == -1 && children > 1)) {
                ap[u] = 1;
            }
        } else if (v != p) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

vi comp[MAXN], adj2[MAXN];
int cnt = 0;

void solve(int u) {
    vis[u] = 1;
    int c = 0, c2 = 0, c3 = ++cnt;
    comp[c3].pb(u);
    for (int v: adj[u]) {
        if (vis[v]) continue;
        if (ap[v]) {
            adj2[c3].pb(cnt+1);
            adj2[cnt+1].pb(c3);
            solve(v);
            continue;
        }
        vi nx;
        deque<int> pq;
        pq.push_back(v);
        int cur = ++cnt;
        adj2[c3].pb(cur);
        adj2[cur].pb(c3);
        while (!pq.empty()) {
            int x = pq.front(); pq.pop_front();
            vis[x] = 1;
            comp[cur].pb(x);
            for (int y: adj[x]) {
                if (vis[y]) continue;
                vis[y] = 1;
                if (ap[y]) {
                    nx.pb(y);
                    continue;
                }
                pq.pb(y);
            }
        }
        for (int k: nx) {
            if (vis[k]) continue;
            adj2[cur].pb(cnt+1);
            adj2[cnt+1].pb(cur);
            solve(k);
        }
    }
}

vi ans;
int i2[MAXN];

void dfs2(int u, int p) {
    for (int v: comp[u]) {
        ans.pb(v);
        i2[v] = ans.size()-1;
    }
    for (int v: adj2[u])
        if (v != p)
            dfs2(v, u);
}

int findP(int x, int y, int i) {
    if (x == y) return 1;
    for (int v: adj[x]) {
        if (i2[v] > i2[x]) {
            int r = findP(v, y, i);
            if (r == 1) return 1;
        }
    }
    return 0;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(0, -1);
    memset(vis, 0, sizeof vis);
    bool fl = false;
    for (int i = 0; i < n; i++) {
        if (ap[i]) {
            solve(i);
            fl = true;
            break;
        }
    }
    /*for (int i = 1; i <= cnt; i++, enl)
        for (int j: comp[i])
            printf("%d ", j);
        pri(cnt);*/
    if (fl) {
        int ind = -1, pre = -1;
        for (int i = 1; i <= cnt; i++)
            if (adj2[i].size() == 1)
                ind = i;
            else if (adj2[i].size() > 2)
                return !printf("IMPOSSIBLE\n");
        dfs2(ind, -1);
        for (int i: ans) {
            int ret = findP(ans[0], i, i);
            if (ret == 0)
                return -1;
        }
        for (int i: ans)
            printf("%d ", i+1);
        enl;
    } else {
        deque<int> pq;
        pq.pb(0);
        while (!pq.empty()) {
            int x = pq.front(); pq.pop_front();
            printf("%d ", x+1);
            vis[x] = 1;
            for (int y: adj[x]) {
                if (vis[y]) continue;
                vis[y] = 1;
                pq.pb(y);
            }
        }
        enl;
    }
    return 0;
}

Test 1

Group: 1, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 1, 5

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 1, 5

Verdict: ACCEPTED

Test 4

Group: 1, 5

Verdict: ACCEPTED

Test 5

Group: 1, 5

Verdict: ACCEPTED

Test 6

Group: 2, 3, 5

Verdict: ACCEPTED

Test 7

Group: 2, 3, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 9

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 10

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Group: 2, 3, 5

Verdict: WRONG ANSWER

Test 12

Group: 2, 3, 5

Verdict: WRONG ANSWER

Test 13

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 14

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 15

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 16

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 17

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 18

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 19

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 20

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 21

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 22

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 23

Group: 3, 5

Verdict: WRONG ANSWER

Test 24

Group: 3, 5

Verdict: WRONG ANSWER

Test 25

Group: 3, 5

Verdict: WRONG ANSWER

Test 26

Group: 3, 5

Verdict: WRONG ANSWER

Test 27

Group: 3, 5

Verdict: WRONG ANSWER

Test 28

Group: 5

Verdict: WRONG ANSWER

Test 29

Group: 5

Verdict: WRONG ANSWER

Test 30

Group: 4, 5

Verdict: WRONG ANSWER

Test 31

Group: 4, 5

Verdict: WRONG ANSWER

Test 32

Group: 4, 5

Verdict: WRONG ANSWER

Test 33

Group: 4, 5

Verdict: WRONG ANSWER

Test 34

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 38

Group: 2, 3, 5

Verdict: ACCEPTED

Test 39

Group: 2, 3, 5

Verdict: ACCEPTED

Test 40

Group: 2, 3, 5

Verdict: ACCEPTED

Test 41

Group: 1, 2, 3, 5

Verdict: ACCEPTED

Test 42

Group: 2, 3, 5

Verdict: WRONG ANSWER

Test 43

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 44

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 45

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 46

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 47

Group: 2, 3, 5

Verdict: WRONG ANSWER

Test 48

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 49

Group: 4, 5

Verdict: WRONG ANSWER