#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
int enc(array<int, 8> &a) {
int b = 0;
for (int i : a) b = 5*b + i;
return b;
}
array<int, 8> dec(int b) {
array<int, 8> a;
for (int i = 7; i >= 0; --i) {
a[i] = b % 5;
b /= 5;
}
return a;
}
void solve() {
int n, m;
cin >> n >> m;
if (m <= 4) {
array<int, 8> a;
for (int i = 0; i < 2*m; ++i) cin >> a[i];
vector<bool> vis(4e5, 0);
vector<int> p(4e5);
vector<pii> mov(4e5);
int b = enc(a);
vis[b] = 1;
p[b] = -1;
queue<int> bfs;
bfs.push(b);
while (bfs.size()) {
b = bfs.front();
bfs.pop();
a = dec(b);
bool g = 1;
for (int i = 0; i < m; ++i) g &= a[2*i] == a[2*i+1];
if (g) {
vector<pii> ans;
while (p[b] != -1) {
ans.push_back(mov[b]);
b = p[b];
}
reverse(ans.begin(), ans.end());
cout << ans.size() << '\n';
for (pii q : ans) cout << q.first << ' ' << q.second << '\n';
return;
}
for (int i = 0; i < m; ++i) if (a[2*i] != 0) {
for (int j = 0; j < m; ++j) if (i != j && a[2*j+1] == 0) {
int x = a[2*i+1] != 0;
int y = a[2*j] != 0;
swap(a[2*i+x], a[2*j+y]);
int c = enc(a);
if (!vis[c]) {
vis[c] = 1;
p[c] = b;
mov[c] = {i+1, j+1};
bfs.push(c);
}
swap(a[2*i+x], a[2*j+y]);
}
}
}
cout << "-1\n";
} else {
vector<array<int, 2>> g(m+1);
vector<vector<int>> pos(n+1);
vector<int> abv(n+1, 0);
set<int> rem;
vector<int> f;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
g[i][0] = a;
g[i][1] = b;
if (a) pos[a].push_back(i);
if (b) pos[b].push_back(i);
if (a != 0 && a != b) {
rem.insert(a);
if (b != 0) rem.insert(b);
}
if (b != 0) ++abv[a];
if (a == 0 && b == 0) f.push_back(i);
}
vector<pii> ans;
set<int> nx;
for (int i = 1; i <= n; ++i) if (rem.count(i) && abv[i] == 0) nx.insert(i);
while (rem.size()) {
if (nx.size()) {
int a = *nx.begin();
int i = pos[a][0];
int j = pos[a][1];
if (g[i][0] == a && g[j][0] == a) {
ans.push_back({j, i});
swap(g[i][1], g[j][0]);
pos[a][1] = i;
f.push_back(j);
} else if (g[i][0] == a && g[j][1] == a) {
ans.push_back({j, i});
swap(g[i][1], g[j][1]);
pos[a][1] = i;
if (--abv[g[j][0]] == 0) nx.insert(g[j][0]);
} else if (g[i][1] == a && g[j][0] == a) {
ans.push_back({i, j});
swap(g[j][1], g[i][1]);
pos[a][0] = i;
if (--abv[g[i][0]] == 0) nx.insert(g[i][0]);
} else {
if (f.empty()) {
cout << "-1\n";
return;
}
int k = f.back();
f.pop_back();
ans.push_back({i, k});
ans.push_back({j, k});
swap(g[k][0], g[i][1]);
swap(g[k][1], g[j][1]);
pos[a][0] = k;
pos[a][1] = k;
if (--abv[g[i][0]] == 0) nx.insert(g[i][0]);
if (--abv[g[j][0]] == 0) nx.insert(g[j][0]);
}
nx.erase(a);
rem.erase(a);
} else {
int a = *rem.begin();
int i = pos[a][0];
int j = pos[a][1];
if (f.empty()) {
cout << "-1\n";
return;
}
int k = f.back();
f.pop_back();
if (g[i][1] == a) {
ans.push_back({i, k});
swap(g[k][0], g[i][1]);
pos[a][0] = k;
if (--abv[g[i][0]] == 0) nx.insert(g[i][0]);
} else {
ans.push_back({j, k});
swap(g[k][0], g[j][1]);
pos[a][1] = k;
if (--abv[g[j][0]] == 0) nx.insert(g[j][0]);
}
}
}
cout << ans.size() << '\n';
for (pii p : ans) cout << p.first+1 << ' ' << p.second+1 << '\n';
}
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 10 |
Correct |
3 ms |
8284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
16820 KB |
Output is correct |
| 2 |
Correct |
161 ms |
19560 KB |
Output is correct |
| 3 |
Correct |
88 ms |
13528 KB |
Output is correct |
| 4 |
Correct |
73 ms |
12608 KB |
Output is correct |
| 5 |
Correct |
172 ms |
19776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 10 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 11 |
Correct |
123 ms |
16820 KB |
Output is correct |
| 12 |
Correct |
161 ms |
19560 KB |
Output is correct |
| 13 |
Correct |
88 ms |
13528 KB |
Output is correct |
| 14 |
Correct |
73 ms |
12608 KB |
Output is correct |
| 15 |
Correct |
172 ms |
19776 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
