#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
int n, m;
vector<int> config[MAXN];
int inv[2*MAXN]; // 2*i+0 for bottom 1 for top
bool vis[MAXN];
typedef pair<int, int> pii;
vector<pii> res;
set<int> avail;
int get_empty() {
if (avail.empty()) {
// assert(false);
cout << -1 << endl;
exit(0);
}
return *avail.begin();
}
void move(int a, int b) {
assert(config[a].size());
assert(config[b].empty() || config[a].back() == (config[b].back()^1));
res.push_back(pii(a+1, b+1));
if (config[b].empty()) avail.erase(b);
config[b].push_back(config[a].back());
config[a].pop_back();
if (config[a].empty()) avail.insert(a);
inv[config[b].back()] = 2*b+config[b].size()-1;
}
void dfs(int cur, bool picky = 0) {
int v = config[cur][0];
int p = inv[v^1]/2;
if (config[p].size() == 1) {
move(p, cur);
return;
}
if (inv[v^1]&1) {
move(p, cur);
return dfs(p, picky);
}
int s = p;
vector<pii> qu;
while (config[s].size() == 2 && !(inv[config[s][1]^1] & 1)) {
int nxt = inv[config[s][1]^1]/2;
qu.push_back(pii(s, nxt));
s = nxt;
}
if (config[s].size() == 2) {
if (picky) return;
int e = get_empty();
move(s, e);
s = e;
}
for (int i = qu.size()-1; i >= 0; i--) move(qu[i].first, qu[i].second);
move(p, cur);
dfs(s, picky);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
if (x > 0) {
config[i].push_back(2*(x-1)+vis[x-1]);
vis[x-1] = 1;
}
if (y > 0) {
config[i].push_back(2*(y-1)+vis[y-1]);
vis[y-1] = 1;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < config[i].size(); j++) {
inv[config[i][j]] = 2*i+j;
}
if (config[i].empty()) avail.insert(i);
}
// first step: combine single bottoms (we do this first because it frees space for free)
// we aren't using compression, so we will have to explicitly check for each single bottom whether it is linked
for (int i = 0; i < m; i++) {
if (config[i].size() == 1) {
dfs(i, 1);
}
}
// now, for each single bottom, combine it (again, this frees space).
// this will always take exactly 1 empty spot, so this is the best option
for (int i = 0; i < m; i++) {
if (config[i].size() == 1) {
dfs(i);
}
}
// nothing else will free up space, so order no longer matters
for (int i = 0; i < m; i++) {
if (config[i].empty()) continue;
assert(config[i].size() == 2);
if (config[i][0] == (config[i][1]^1)) continue;
int e = get_empty();
move(i, e);
dfs(i, 0);
}
for (int i = 0; i < m; i++) assert(config[i].empty() || (config[i].size() == 2 && (config[i][0]^1) == config[i][1]));
cout << res.size() << '\n';
for (pii p: res) {
cout << p.first << ' ' << p.second << '\n';
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int j = 0; j < config[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Runtime error |
7 ms |
9952 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
52 ms |
25972 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
10108 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
10108 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
10032 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Runtime error |
7 ms |
9952 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
