#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// My bug list :
// integer overflow
// 0based, 1based forgotten
// index out of bound
// n, m, i, j typo
// some cases are missing
const int MAX_N = 300010;
int n, m;
vector<int> stk[MAX_N], emp;
vector<int> at[MAX_N];
void fail() {
cout << -1 << '\n';
exit(0);
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 0;i < m;++i) {
int b, t;
cin >> b >> t;
for (int j : {b, t}) if (j) {
stk[i].pb(j);
at[j].pb(i);
}
if (b == 0) emp.pb(i);
}
vector<pair<int,int>> res;
// all full or empty
//
// vector<pair<int,int>> ud;
auto hp = [&]() {
DE("stk");
for (int i = 0;i < m;++i)
debug(AI(stk[i]));
};
auto atob = [&](int a, int b) {
int v = stk[a].back(); stk[a].pop_back();
stk[b].pb(v);
*find(AI(at[v]), a) = b;
res.pb(a, b);
};
auto other = [&](int x, int p) {
return at[x][0] + at[x][1] - p;
};
auto shift = [&](int p) {
assert(stk[p].size() == 1);
int v = stk[p][0], o = other(v, p);
while (stk[o].size() == 2 && stk[o][1] == v) {
atob(o, p);
p = o;
v = stk[p][0];
o = other(v, p);
}
return p;
};
auto eqtop = [&](int p) {
int v = stk[p][1], o = other(v, p);
while (stk[o][0] == v) {
p = o;
v = stk[p][1], o = other(v, p);
}
return p;
};
function<void(int)> take_care = [&](int p) {
if (emp.empty()) fail();
if (stk[p].empty()) {
emp.pb(p);
return;
}
assert(stk[p].size() == 1);
int v = stk[p][0];
int e = emp.back(), o = other(v, p);
if (stk[o].size() == 1 || stk[o][1] == v) {
atob(o, p);
take_care(o);
return;
}
int g = eqtop(o);
atob(g, e);
shift(g);
atob(o, p);
emp.back() = o;
take_care(e);
};
function<void(int)> no_more_care = [&](int p) {
if (stk[p].empty()) {
emp.pb(p);
return;
}
assert(stk[p].size() == 1);
int v = stk[p][0];
int o = other(v, p);
if (stk[o].back() == v) {
atob(o, p);
no_more_care(o);
}
};
for (int i = 0;i < m;++i) if (stk[i].size() == 1) {
no_more_care(i);
}
//hp();
for (int i = 0;i < m;++i) if (stk[i].size() == 1)
take_care(i);
// int x = stk[i][0];
// if (stk[other(x, i)].back() == x)
// take_
for (int i = 1;i <= n;++i) {
int a = at[i][0], b = at[i][1];
if (a == b) continue;
if (stk[a].size() + stk[b].size() == 4 &&
(stk[a].back() == i && stk[b].back() == i) {
if (emp.empty()) fail();
int e = emp.back(); emp.pop_back();
atob(a, e);
atob(b, e);
a = shift(a), b = shift(b);
if (stk[a][0] == stk[b][0]) {
atob(a, b);
emp.pb(a);
} else {
take_care(a);
}
}
}
for (int i = 1;i <= n;++i) {
int a = at[i][0], b = at[i][1];
if (a == b) continue;
if (emp.empty()) fail();
if (stk[a][0] != i) swap(a, b);
// stk[a][0] = i
int e = emp.back();
atob(a, e);
int g = shift(a);
atob(e, g);
// must be one up and one down
}
for (int i = 1;i <= n;++i) assert(at[i][0] == at[i][1]);
cout << res.size() << '\n';
for (auto [a, b] : res) {
++a, ++b;
cout << a << ' ' << b << '\n';
}
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
Main.cpp:51:5: note: in expansion of macro 'DE'
51 | DE("stk");
| ^~
Main.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
Main.cpp:53:7: note: in expansion of macro 'debug'
53 | debug(AI(stk[i]));
| ^~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:132:49: error: expected ')' before '{' token
132 | (stk[a].back() == i && stk[b].back() == i) {
| ^~
| )
Main.cpp:131:8: note: to match this '('
131 | if (stk[a].size() + stk[b].size() == 4 &&
| ^
Main.cpp:145:3: error: expected primary-expression before '}' token
145 | }
| ^
