Graph Ordering

input/code.cpp: In function 'int main()':
input/code.cpp:133:7: 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:137:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

#include <bits/stdc++.h>
using namespace std;
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
typedef long long ll;
typedef long double ld;
const int MAXN = 100005;
const int MAXM = 200005;
vector<int> E[MAXN];
pair<int, int> edges[MAXM];
namespace blockcut {
vector<int> preorder;
int low[MAXN]; // topmost vertex a descendent can reach via back-edge
int H[MAXN];
bool cut[MAXN]; // cut[x] -> x is a cut vertex
int parent[MAXN];
vector<int> blocke[MAXN]; // all edges in a block
vector<int> blockv[MAXN]; // all vertices in a block
// a tree-edge is rep by the deeper vertex. a block is rep by highest tree edge.
int vblock[MAXN]; // block of the parent-edge (vblock[1] = 0, vblock[blockId] = blockId)
int eblock[MAXM]; // block of edge
vector<int> adjBlock[MAXN]; // cut nodes adjacent to a block
vector<int> adjCut[MAXN]; // blocks adjacent to a cut node, empty means not cut
void go(int x) {
	preorder.push_back(x);
	low[x] = x;
	int totch = 0;
	for (auto y : E[x]) {
		if (H[y] == -1) {
			H[y] = H[x] + 1;
			parent[y] = x;
			++totch;
			go(y);
			if (H[low[y]] < H[low[x]]) low[x] = low[y];
			if (H[low[y]] >= H[x]) cut[x] = true;
		} else if (H[y] < H[x] - 1) {
			// This is a backedge that is not to the parent
			if (H[y] < H[low[x]]) low[x] = y;
		}
	}
	if (x == 1 && totch > 1) cut[x] = true;
}
void getBlocks(int n, int m) {
	memset(H, -1, sizeof(H));
	H[1] = 0;
	go(1);
	for (int x : preorder) {
		if (!parent[x]) continue;
		if (H[low[x]] < H[parent[x]]) vblock[x] = vblock[parent[x]];
		else vblock[x] = x;
	}
	for (int i = 0; i < m; ++i) {
		auto e = edges[i];
		int deeper = H[e.first] > H[e.second] ? e.first : e.second;
		eblock[i] = vblock[deeper];
	}
	for (int i = 0; i < m; ++i) {
		blocke[eblock[i]].push_back(i);
		blockv[eblock[i]].push_back(edges[i].first);
		blockv[eblock[i]].push_back(edges[i].second);
	}
	// If we need the block-cut tree; this takes n log n
	for (int i = 1; i <= n; ++i) {
		sort(blockv[i].begin(), blockv[i].end());
		blockv[i].erase(unique(blockv[i].begin(), blockv[i].end()), blockv[i].end());
		for (int x : blockv[i]) {
			if (cut[x]) {
				adjCut[x].push_back(i);
				adjBlock[i].push_back(x);
			}
		}
	}
}
};
namespace bipolar {
int H[MAXN];
int low[MAXN];
void dfs(int x) {
	low[x] = x;
	for (auto y : E[x]) {
		if (H[y] == -1) {
			H[y] = H[x] + 1;
			dfs(y);
			if (H[low[y]] < H[low[x]]) low[x] = low[y];
		} else if (H[y] < H[x] - 1) {
			// This is a backedge that is not to the parent
			if (H[y] < H[low[x]]) low[x] = y;
		}
	}
}
bool vis[MAXN];
bool isBefore[MAXN];
list<int> ordering;
list<int>::iterator vpos[MAXN];
void dfsOrder(int x, int p = -1) {
	vis[x] = true;
	if (low[x] != x) { // low[x] == x should only occur for vertex s
		if (isBefore[low[x]]) {
			vpos[x] = ordering.insert(vpos[p], x);
		} else {
			vpos[x] = ordering.insert(next(vpos[p]), x);
		}
		// Update isBefore for relation (parent[x], x)
		isBefore[p] = !isBefore[low[x]];
	}
	for (auto y : E[x])
		if (!vis[y]) dfsOrder(y, x);
}
// NOTE: this modifies edges array E!
void getOrdering(int n, int s, int t) {
	if (n == 2) {
		ordering = {1, 2};
		return;
	}
	memset(H, -1, sizeof(H));
	H[s] = 0;
	// Make sure t is first neighbor of s
	E[s].insert(E[s].begin(), t);
	E[t].push_back(s);
	dfs(s);
	isBefore[s] = false;
	vpos[s] = ordering.insert(ordering.end(), s);
	dfsOrder(s);
}
};
using namespace blockcut;
using namespace bipolar;
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	map<pair<int, int>, int> mp;
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
		edges[i] = {a, b};
		mp[{a, b}] = mp[{b, a}] = i;
	}
	getBlocks(n, m);
	int s = -1, t = -1;
	// Every cut node has <= two neighboring blocks.
	for (int i = 1; i <= n; ++i) {
		if (adjCut[i].size() > 2) {
			printf("IMPOSSIBLE\n");
			return 0;
		}
	}
	// Get two blocks adjacent to only 1 cut node
	for (int i = 1; i <= n; ++i) {
		if (adjBlock[i].size() == 1) {
			assert(blockv[i].size() >= 2);
			int x = cut[blockv[i][0]] ? blockv[i][1] : blockv[i][0];
			if (s == -1) s = x;
			else t = x;
		}
	}
	if (s == -1) {
		s = 1;
		t = 2;
	}
	getOrdering(n, s, t);
	for (int x : ordering) printf("%d ", x);
}

Test 1

Group: 1, 4, 5

Verdict: WRONG ANSWER

Test 2

Group: 1, 5

Verdict: ACCEPTED

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: ACCEPTED

Test 8

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 9

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 2, 3, 5

Verdict: WRONG ANSWER

Test 12

Group: 2, 3, 5

Verdict: ACCEPTED

Test 13

Group: 2, 3, 4, 5

Verdict: RUNTIME ERROR

Test 14

Group: 2, 3, 4, 5

Verdict: RUNTIME ERROR

Test 15

Group: 2, 3, 4, 5

Verdict: RUNTIME ERROR

Test 16

Group: 2, 3, 4, 5

Verdict: RUNTIME ERROR

Test 17

Group: 2, 3, 4, 5

Verdict: RUNTIME ERROR

Test 18

Group: 2, 3, 4, 5

Verdict: RUNTIME ERROR

Test 19

Group: 3, 4, 5

Verdict: RUNTIME ERROR

Test 20

Group: 3, 4, 5

Verdict: RUNTIME ERROR

Test 21

Group: 3, 4, 5

Verdict: ACCEPTED

Test 22

Group: 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 3, 5

Verdict: ACCEPTED

Test 24

Group: 3, 5

Verdict: ACCEPTED

Test 25

Group: 3, 5

Verdict: ACCEPTED

Test 26

Group: 3, 5

Verdict: ACCEPTED

Test 27

Group: 3, 5

Verdict: ACCEPTED

Test 28

Group: 5

Verdict: ACCEPTED

Test 29

Group: 5

Verdict: ACCEPTED

Test 30

Group: 4, 5

Verdict: ACCEPTED

Test 31

Group: 4, 5

Verdict: ACCEPTED

Test 32

Group: 4, 5

Verdict: ACCEPTED

Test 33

Group: 4, 5

Verdict: ACCEPTED

Test 34

Group: 5

Verdict: ACCEPTED

Test 35

Group: 5

Verdict: ACCEPTED

Test 36

Group: 5

Verdict: ACCEPTED

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: WRONG ANSWER

Test 40

Group: 2, 3, 5

Verdict: ACCEPTED

Test 41

Group: 1, 2, 3, 5

Verdict: ACCEPTED

Test 42

Group: 2, 3, 5

Verdict: ACCEPTED

Test 43

Group: 3, 4, 5

Verdict: RUNTIME ERROR

Test 44

Group: 3, 4, 5

Verdict: RUNTIME ERROR

Test 45

Group: 2, 3, 4, 5

Verdict: RUNTIME ERROR

Test 46

Group: 2, 3, 4, 5

Verdict: RUNTIME ERROR

Test 47

Group: 2, 3, 5

Verdict: RUNTIME ERROR

Test 48

Group: 3, 4, 5

Verdict: RUNTIME ERROR

Test 49

Group: 4, 5

Verdict: RUNTIME ERROR