#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mx = 1e5 + 5;
void solve() {
int n, m; cin >> n >> m;
vector<vector<int>> v(m, vector<int>(2, 0));
vector<vector<int>> pos(n);
vector<int> empty;
vector<pair<int, int>> res;
for (int i = 0; i < m; i++) {
auto& x = v[i];
cin >> x[0] >> x[1]; x[0]--; x[1]--;
if (x[0] + 1) pos[x[0]].push_back(i);
if (x[1] + 1) pos[x[1]].push_back(i);
if (x[0] + x[1] == -2) empty.push_back(i);
}
vector<int> vis(n, 0);
auto mov = [&](int x, int y) -> void {
res.push_back({ x, y });
if (v[x][1] + 1) {
if (v[y][0] + 1) swap(v[x][1], v[y][1]);
else swap(v[x][1], v[y][0]);
} else {
if (v[y][0] + 1) swap(v[x][0], v[y][1]);
else swap(v[x][0], v[y][0]);
}
};
//case 1: trivial case
auto good = [&](int x) -> bool {
for (int i = 0; i < 2; i++) {
if (v[pos[x][0]][1] == -1 && (v[pos[x][1]][1] == x || v[pos[x][1]][1] == -1)) {
return true;
}
swap(pos[x][0], pos[x][1]);
}
return false;
};
vector<int> q;
for (int i = 0; i < n; i++) {
if (pos[i][0] == pos[i][1]) {
vis[i] = 1;
continue;
}
if (good(i)) {
q.push_back(i); vis[i] = 1;
}
}
while (!q.empty()) {
auto x = q.back();
q.pop_back();
// cout << "good: " << x << endl;
mov(pos[x][1], pos[x][0]);
auto t = v[pos[x][1]][0];
if (t != -1 && good(t)) { vis[t] = 1; q.push_back(t); }
}
vector<int> todo;
bool bad = 0;
auto clear = [&](int t) {
if (t == -1) return;
for (int j = 0; j < 2; j++) {
// cout << t << "," << pos[t][0] << "," << v[pos[t][0]][1] << endl;
if (v[pos[t][0]][1] == -1) {
while (true) {
//cout << "t: " << t << endl;
if (t != -1) vis[t] = 1;
if (t == -1) {
//process
reverse(todo.begin(), todo.end());
empty.push_back(pos[todo.back()][0]);
for (auto& x : todo) {
mov(pos[x][0], pos[x][1]);
}
todo.clear();
return;
} else if (v[pos[t][1]][1] == t) {
if (v[pos[t][0]][1] == t) {
if (!empty.size()) { bad = 1; return; }
mov(pos[t][0], empty.back());
mov(pos[t][1], empty.back());
empty.pop_back();
//process
reverse(todo.begin(), todo.end());
empty.push_back(pos[todo.back()][0]);
for (auto& x : todo) {
mov(pos[x][0], pos[x][1]);
}
todo.clear();
} else {
mov(pos[t][1], pos[t][0]);
}
t = v[pos[t][1]][0];
if (v[pos[t][0]][1] != -1) swap(pos[t][0], pos[t][1]);
} else {
todo.push_back(t); vis[t] = 1;
int p = t;
t = v[pos[t][1]][1];
if (t != -1 && v[pos[t][0]][0] != p) swap(pos[t][0], pos[t][1]);
}
}
}
swap(pos[t][0], pos[t][1]);
}
};
//cout << "case2" << endl;
//case 2 - strip
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
int t = i;
clear(t);
if (bad) return;
}
//cout << "case3" << endl;
//case 3 - circle
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
int t = i;
if (v[pos[t][0]][1] == t && v[pos[t][1]][1] == t) {
vis[t] = 1;
if (!empty.size()) { cout << -1 << endl;return; }
mov(pos[t][0], empty.back());
mov(pos[t][1], empty.back());
empty.pop_back();
t = v[pos[t][0]][0];
clear(t); if (bad) return;
}
}
// cout << "case4" << endl;
//case 4 - finish them
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
int t = i; vis[t] = 1;
if (v[pos[t][0]][1] != t) swap(pos[t][0], pos[t][1]);
if (!empty.size()) { cout << -1 << endl;return; }
int bk = empty.back();
mov(pos[t][0], bk); pos[t][0] = bk;
t = v[pos[t][0]][0];
clear(t);
if (bad) return;
}
cout << res.size() << endl;
for (auto& x : res) cout << x.first + 1 << " " << x.second + 1 << endl;
//cout << "result: " << endl;
//for (auto& x : v) cout << x[0] + 1 << " " << x[1] + 1 << endl;
}
int32_t main() {
int t = 1;
//cin >> t;
while (t--)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
20156 KB |
Output is correct |
| 2 |
Correct |
236 ms |
20772 KB |
Output is correct |
| 3 |
Correct |
165 ms |
18288 KB |
Output is correct |
| 4 |
Correct |
156 ms |
17972 KB |
Output is correct |
| 5 |
Correct |
214 ms |
21024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
304 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int32 expected |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
304 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int32 expected |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int32 expected |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
