Dominoes

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <class T> T edmondsKarp(vector<unordered_map<int, T>> & graph, int source, int sink) {
	assert(source != sink);
	T flow = 0;
	vi par(sz(graph)), q = par;

	for (;;) {
		fill(all(par),  -1);
		par[source] = 0;
		int ptr = 1;
		q[0] = source;

		rep(i,0,ptr) {
			int x = q[i];
			for (auto e : graph[x]) {
				if (par[e.first] == -1 && e.second > 0) {
					par[e.first] = x;
					q[ptr++] = e.first;
					if (e.first == sink) goto out;
				}
			}
		}

		return flow;
	out:
		T inc = numeric_limits<T>::max();
		for (int y = sink; y != source; y = par[y])
			inc = min(inc, graph[par[y]][y]);
		flow += inc;
		for (int y = sink; y != source; y = par[y]) {
			int p = par[y];
			if ((graph[p][y] -= inc) <= 0) graph[p].erase(y);
			graph[y][p] += inc;
		}
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int n;
	cin >> n;
	int c[36] {};
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		c[a + 6 * b]++;
	}
	const int source = 0;
	const int A = 1;
	const int B = A + 36;
	const int sink = B + 36;
	vector<unordered_map<int, int>> g(1 + 36 + 36 + 1);
	for (int i = 0; i < 36; ++i) {
		g[source][A + i] = 1;
		g[B + i][sink] = 1;
	}
	for (int i = 0; i < 36; ++i) {
		for (int j = 0; j < 36; ++j) {
			if (!c[i] || !c[j]) continue;
			if (i / 6 != j % 6) {
				g[A + i][B + j] = i != j ? 1 : 0;
			}
		}
	}
	auto og = g;
	int flow = edmondsKarp(g, source, sink);
	int m = 0;
	for (int i = 0; i < 36; ++i) m += !!c[i];
	if (flow < m - 1) {
		cout << "Impossible" << endl;
		return 0;
	}
	int nxt[36][36] {}, indeg[36] {};
	for (int i = 0; i < 36; ++i) {
		for (int j = 0; j < 36; ++j) {
			nxt[i][j] = max(0, og[A + i][B + j] - g[A + i][B + j]);
			indeg[j] += nxt[i][j];
			if (nxt[i][j]) {
			}
		}
	}
	int s = 0;
	while (!c[s]) ++s;
	for (int i = 0; i < 36; ++i) {
		if (c[i] && indeg[i] == 0) {
			s = i;
		}
	}
	vi ans;
	auto dfs = [&](auto dfs, int i, int d) -> bool {
		if (d == m) {
			ans.push_back(i);
			return true;
		}
		for (int j = 0; j < 36; ++j) {
			if (nxt[i][j] > 0) {
				nxt[i][j]--;
				bool r = dfs(dfs, j, d + 1);
				if (r) {
					ans.push_back(i);
					return true;
				}
				nxt[i][j]++;
			}
		}
		return false;
	};
	// cout << s % 6 << " " << s / 6 << endl;
	dfs(dfs, s, 1);
	reverse(all(ans));
	for (int i : ans) {
		while (c[i]--) {
			cout << i % 6 + 1 << ' ' << i / 6 + 1 << ' ';
		}
	}
	cout << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER