考虑把这个停车位当作栈来考虑，每次可以取出栈顶放到另一个栈，并且要保证另一个栈 \(sz\le 2\)，且当 \(sz = 2\) 时要保证栈顶栈底都是同一种元素。
令 \((x, y)\) 表示 \(x\) 为栈顶 \(y\) 为栈底，\((0, x)\) 表示栈中元素只有 \(x\)。
考虑对于 \((x, y)\)，连一条 \(x\to y\) 的边，若栈中元素数量 \(= 1\) 就不连。
那么对于连边出来的一条链，相当于是 \((0, x), (x, y), (y, z)\) 这样的，那么可以通过 \(len - 1\) 次操作变为 \((x, x), (y, y), (0, z)\)。
同时对于 \((0, p), (0, p)\)，可以合并出 \((p, p), (0, 0)\)，就多了一个空栈。
因为这种操作是不需要空栈的，所以可以先把这些操作做了。
还有可能是个环的样子，那么相当于是 \((x, y), (y, z), (z, x)\)。
那么这个可以用一个空栈，先变为 \((0, y), (y, z), (z, x), (0, x)\)，再变为 \((y, y), (z, z), (0, x), (0, x)\)，再合并一下变为 \((y, y), (z, z), (x, x), (0, 0)\)。
用 \(sz + 1\) 次操作即可做完。
同时考虑剩下的只可能是 \((0, x)\) 或者 \((x, y), (x, z), (y, p), (z, q)\) 之类的。
首先对于前面的不考虑。
对于后面的，只需要一个空栈放入 \((x, x)\)，剩下就变成两条链 \((0, y), (y, p)\) 和 \((0, z), (z, q)\)。
那么就可以把链做完了。
但是能发现若对于 \(p, q\)，存在 \((0, p)\)，那么在拆完后就还能得到一个 \((p, p), (0, 0)\)，返回一个空栈。
于是可以按照一个优先级来选，即拆完后能得到的空栈越多优先级就越高。
当然也可以考虑对于叶子节点 \(p, q\) 连边。
那么只会有链和环的情况。
其中链是每一步都能还一个空栈，最后一步能还两个；环是第一步不还，最后一步还两个，其他还一个。
所以能发现先删链再删环是更优的。
能发现对于刚刚的构造方式，如果能不移是肯定不会移的，所以操作次数肯定是最少的。
时间复杂度 \(\mathcal{O}(n)\)。
#include<bits/stdc++.h>
const int maxn = 2e5 + 10;
int n, m;
int sx[maxn], sy[maxn];
std::vector<std::pair<int, int> > ans;
inline void Solve(int x, int y) {
ans.emplace_back(x, y);
assert(sy[x]), assert(! sx[y]);
int &s = sx[x] ? sx[x] : sy[x], &t = sy[y] ? sx[y] : sy[y];
t = s, s = 0;
assert(! sx[y] || sx[y] == sy[y]);
}
namespace Solve1 {
std::vector<int> to[maxn];
int in[maxn], w[maxn];
inline void Main() {
for (int i = 1; i <= n; i++)
to[i].clear(), in[i] = 0, w[i] = 0;
for (int i = 1; i <= m; i++) {
if (sx[i] && sx[i] != sy[i])
to[sx[i]].push_back(i), in[sy[i]]++;
if (! sx[i] && sy[i])
w[sy[i]] = i;
}
for (int i = 1; i <= n; i++)
if (! in[i] && to[i].size() == 1) {
int l = w[i];
for (int u = i; ; u = sy[to[u][0]]) {
if (to[u].empty()) break;
Solve(to[u][0], l), l = to[u][0];
}
}
for (int i = 1; i <= n; i++)
w[i] = 0;
for (int i = 1; i <= m; i++) {
if (sx[i] || ! sy[i]) continue;
if (w[sy[i]]) Solve(i, w[sy[i]]);
else w[sy[i]] = i;
}
}
}
namespace Solve2 {
std::vector<int> to[maxn];
bool vis[maxn];
inline bool Main() {
for (int i = 1; i <= n; i++)
to[i].clear(), vis[i] = 0;
for (int i = 1; i <= m; i++)
if (sx[i] && sx[i] != sy[i])
to[sx[i]].push_back(i);
int e = 0;
for (int i = 1; i <= m; i++)
if (! sx[i] && ! sy[i])
e = i;
for (int s = 1; s <= n; s++) {
if (vis[s]) continue;
std::vector<int> P;
bool f = 1; int u = s;
do {
if (vis[u]) {f = 0; break;}
vis[u] = 1;
if (to[u].size() != 1) {f = 0; break;}
P.push_back(to[u][0]), u = sy[to[u][0]];
} while (u != s);
if (! f) continue;
if (! e) return false;
Solve(P[0], e);
for (int i = 0; i + 1 < P.size(); i++)
Solve(P[i + 1], P[i]);
Solve(e, P.back());
}
return true;
}
}
namespace Solve3 {
std::vector<int> to[maxn], G[maxn];
int tx[maxn], ty[maxn], w[maxn];
inline bool Main() {
for (int i = 1; i <= n; i++)
to[i].clear(), G[i].clear(), w[i] = 0;
std::vector<int> e;
for (int i = 1; i <= m; i++) {
if (sx[i] && sx[i] != sy[i])
to[sx[i]].push_back(i);
if (! sx[i] && sy[i])
w[sy[i]] = i;
if (! sx[i] && ! sy[i])
e.push_back(i);
}
for (int i = 1; i <= n; i++)
if (to[i].size() == 2) {
tx[i] = sy[to[i][0]], ty[i] = sy[to[i][1]];
while (to[tx[i]].size()) tx[i] = sy[to[tx[i]][0]];
while (to[ty[i]].size()) ty[i] = sy[to[ty[i]][0]];
G[tx[i]].push_back(i), G[ty[i]].push_back(i);
}
auto DO = [&](int s) {
for (int l = s; ; ) {
int i = G[l][0];
int idx = to[i][0], idy = to[i][1];
if (e.empty())
return false;
int we = e.back(); e.pop_back();
Solve(idx, we), Solve(idy, we);
while (to[sy[idx]].size())
Solve(to[sy[idx]][0], idx), idx = to[sy[idx]][0];
while (to[sy[idy]].size())
Solve(to[sy[idy]][0], idy), idy = to[sy[idy]][0];
if (w[tx[i]]) Solve(idx, w[tx[i]]), e.push_back(idx);
else w[tx[i]] = idx;
if (w[ty[i]]) Solve(idy, w[ty[i]]), e.push_back(idy);
else w[ty[i]] = idy;
G[tx[i]].erase(std::find(G[tx[i]].begin(), G[tx[i]].end(), i));
G[ty[i]].erase(std::find(G[ty[i]].begin(), G[ty[i]].end(), i));
if (G[tx[i]].empty() && G[ty[i]].empty())
break;
l = G[tx[i]].empty() ? ty[i] : tx[i];
}
return true;
};
for (int s = 1; s <= n; s++)
if (G[s].size() == 1)
if (! DO(s)) return false;
for (int s = 1; s <= n; s++)
if (G[s].size() == 2)
if (! DO(s)) return false;
return true;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, k; i <= m; i++) scanf("%d%d", &sy[i], &sx[i]);
Solve1::Main();
if (! Solve2::Main())
return puts("-1"), 0;
if (! Solve3::Main())
return puts("-1"), 0;
for (int i = 1; i <= n; i++)
assert(sx[i] == sy[i]);
printf("%zu\n", ans.size());
for (auto _ : ans)
printf("%d %d\n", _.first, _.second);
return 0;
}