#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 11;
map<int, vector<int>> pos;
struct slot{
int id, a[2], cnt = 0;
int count(){ cnt = 0; if(a[0] != 0) cnt++; if(a[1] != 0) cnt++; return cnt; }
int top(){ if(cnt == 0) return 0; return a[cnt - 1]; }
void remove(){ assert(cnt != 0); pos[a[cnt - 1]].erase(find(pos[a[cnt - 1]].begin(), pos[a[cnt - 1]].end(), id)); a[--cnt] = 0; }
void add(int x, bool init = false){ assert(cnt != 2); assert(init || !(cnt == 1 && a[0] != x)); pos[x].push_back(id); a[cnt++] = x; }
bool same(){ return a[0] == a[1] && a[0] != 0; }
int other(int x){ assert(count() == 2); return a[0] + a[1] - x; }
} S[MAXN];
void failure(){
cout << -1 << endl;
exit(0);
}
int n, m;
bool done[MAXN];
vector<pair<int, int>> ans;
map<int, vector<int>> tops, bottoms;
vector<int> immediate, single, both_top, empty_space;
void move(int x, int y){
// printf("move: %d => %d\n", x, y);
assert(1 <= x && x <= m && 1 <= y && y <= m && x != y);
S[y].add(S[x].top()); S[x].remove();
ans.push_back({x, y});
if(S[x].count()){
tops[S[x].top()].push_back(x);
bottoms[S[x].top()].push_back(x);
if(tops[S[x].top()].size() == 2){
immediate.push_back(S[x].top());
}
}else{
empty_space.push_back(x);
}
if(S[y].count() == 1){
bottoms[S[y].top()].push_back(y);
if(tops[S[y].top()].size() == 2){
immediate.push_back(S[y].top());
}
}
if(S[y].same()){
done[S[y].top()] = true;
}
}
void print(){
for(int i = 1; i >= 0; i--){
for(int j = 1; j <= m; j++){
cout << S[j].a[i] << " \n"[j == m];
}
}
}
int32_t main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y; cin >> x >> y;
S[i].id = i;
if(x != 0) S[i].add(x);
if(y != 0) S[i].add(y, true);
}
for(int i = 1; i <= m; i++){
if(S[i].same()){
done[S[i].top()] = true;
continue;
}
if(S[i].count() == 0){
empty_space.push_back(i);
}else{
tops[S[i].top()].push_back(i);
if(S[i].count() == 1){
bottoms[S[i].top()].push_back(i);
single.push_back(S[i].top());
}
}
}
for(auto [x, v] : bottoms){
if(tops[x].size() == 2){
immediate.push_back(x);
}
}
for(auto [x, v] : tops){
if(v.size() == 2){
both_top.push_back(x);
}
}
int not_done = 1;
while(not_done <= n){
if(immediate.size()){
int x = immediate.back(); immediate.pop_back();
if(done[x]) continue;
vector<int> top = tops[x];
vector<int> bottom = bottoms[x];
int from = top[0] == bottom[0] ? top[1] : top[0];
int to = bottom[0];
move(from, to);
continue;
}
if(empty_space.size() && single.size()){
int x = single.back(); single.pop_back();
if(done[x]) continue;
vector<int> st;
vector<int> p = pos[x];
assert(p.size() == 2);
if(S[p[1]].count() == 1) swap(p[0], p[1]);
assert(S[p[1]].count() == 2);
st.push_back(S[p[1]].other(x));
while(true){
int y = st.back();
vector<int> p2 = pos[y];
assert(p2.size() == 2);
if(S[p2[0]].top() == y && S[p2[1]].top() == y) break;
if(S[p2[0]].top() == y) swap(p2[0], p2[1]);
st.push_back(S[p2[0]].top());
}
int e = empty_space.back(); empty_space.pop_back();
vector<int> p3 = pos[st.back()];
move(p3[0], e);
move(p3[1], e);
continue;
}
if(empty_space.size() && both_top.size()){
int x = both_top.back(); both_top.pop_back();
if(done[x]) continue;
int e = empty_space.back(); empty_space.pop_back();
vector<int> p3 = pos[x];
move(p3[0], e);
move(p3[1], e);
continue;
}
while(done[not_done] && not_done <= n) not_done++;
if(empty_space.size() && not_done <= n){
int x = not_done;
int e = empty_space.back(); empty_space.pop_back();
vector<int> p = pos[x];
if(S[p[0]].top() != x) swap(p[0], p[1]);
move(p[0], e);
continue;
}
if(not_done <= n) failure();
}
// print();
cout << ans.size() << endl;
for(auto [x, y] : ans){
cout << x << ' ' << y << endl;
}
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:91:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
91 | for(auto [x, v] : bottoms){
| ^
Main.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | for(auto [x, v] : tops){
| ^
Main.cpp:161:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
161 | for(auto [x, y] : ans){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3436 KB |
Output is correct |
| 4 |
Runtime error |
4 ms |
6740 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
426 ms |
33336 KB |
Output is correct |
| 2 |
Correct |
580 ms |
40156 KB |
Output is correct |
| 3 |
Correct |
335 ms |
25932 KB |
Output is correct |
| 4 |
Correct |
258 ms |
24184 KB |
Output is correct |
| 5 |
Correct |
574 ms |
39572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
3668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3540 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3668 KB |
Output is correct |
| 4 |
Runtime error |
5 ms |
7124 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3436 KB |
Output is correct |
| 4 |
Runtime error |
4 ms |
6740 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
