#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int MAXN = 400005;
int n, m, moze = 1;
int b[MAXN], t[MAXN], fa[MAXN], siz[MAXN], InCycle[MAXN], TPCnt[MAXN],
cnt[MAXN];
set<int> Free, G[MAXN];
vector<int> Loc[MAXN];
vector<pair<pi, int> > red;
vector<pi> sol;
void move(int x, int y) {
sol.push_back({x, y});
if (++cnt[y] == 1) Free.erase(y);
if (--cnt[x] == 0) Free.insert(x);
}
int find_set(int x) { return x == fa[x] ? x : fa[x] = find_set(fa[x]); }
void add_edge(int x, int y) {
G[x].insert(y), G[y].insert(x);
TPCnt[y] += (x % 2) && (y % 2);
x = find_set(x), y = find_set(y);
if (x == y)
InCycle[x] = 1;
else
fa[x] = y, siz[y] += siz[x], TPCnt[y] += TPCnt[x];
}
void remove_edge(int x, int y) { G[x].erase(y), G[y].erase(x); }
int get_end_of_chain(int x, int last) {
if (G[x].size() == 1) return x;
assert(G[x].size() == 2);
for (auto v : G[x])
if (v != last) return get_end_of_chain(v, x);
return -1;
}
void solve_path(int idx) {
int curr = get_end_of_chain(idx, -1), last = -1;
vector<int> r;
while (curr != -1) {
r.push_back(curr);
int nxt = -1;
for (auto v : G[curr]) {
if (v == last) continue;
nxt = v;
}
last = curr, curr = nxt;
}
for (int i = 0, sz = r.size(); i < sz; i++) {
if (r[i + 1] % 2 == 1) {
move(r[i + 1] / 2, r[i] / 2);
i++;
} else {
int k = -1;
for (int j = i; j < sz - 1; j++) {
if (r[j] % 2 == 1 && r[j + 1] % 2 == 1) {
k = j;
break;
}
}
if (k != -1) {
if (Free.empty()) {
moze = 0;
return;
}
int to = *Free.begin();
move(r[k] / 2, to), move(r[k + 1] / 2, to);
for (int j = k - 1; j >= i; j -= 2) move(r[j - 1] / 2, r[j] / 2);
i = k + 1;
} else {
for (int j = sz - 1; j > i + 1; j -= 2) move(r[j - 1] / 2, r[j] / 2);
move(r[i] / 2, r[i + 1] / 2);
break;
}
}
}
}
void solve_cycle(int idx) {
if (Free.size() == 0) {
moze = 0;
return;
}
int pocetak = idx, curr = idx, last = -1;
vector<int> r;
while (curr != -1) {
r.push_back(curr);
int nxt = -1;
for (auto v : G[curr]) {
if (v == last || v == pocetak) continue;
nxt = v;
}
last = curr;
curr = nxt;
}
int R = r.size();
int k = -1;
for (int i = 0; i < R; i++) {
if (r[i] % 2 == 1) k = i;
if (r[i] % 2 == 1 && r[(i + 1) % R] % 2 == 1) {
k = i;
break;
}
}
int x = r[k], y = r[(k + 1) % R];
if (y % 2 == 1) {
int to = *Free.begin();
move(x / 2, to);
move(y / 2, to);
remove_edge(r[(k - 1 + R) % R], r[k]);
remove_edge(r[k], r[(k + 1) % R]);
remove_edge(r[(k + 1) % R], r[(k + 2) % R]);
solve_path(r[(k + 2) % r.size()]);
} else {
int to = *Free.begin();
if (x / 2 != y / 2) {
move(x / 2, to);
for (int i = 2; i < R; i += 2) {
move(r[(k - i + R) % R] / 2, r[(k - i + 1 + R) % R] / 2);
}
move(y / 2, to);
} else {
move(x / 2, to);
for (int i = 1; i + 1 < R; i += 2) {
move(r[(k + i + 1) % R] / 2, r[(k + i) % R] / 2);
}
move(r[(k - 1 + R) % R] / 2, to);
}
}
}
void ispis() {}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> b[i] >> t[i];
if (b[i]) Loc[b[i]].push_back(2 * i);
if (t[i]) Loc[t[i]].push_back(2 * i + 1);
fa[2 * i] = 2 * i, siz[2 * i] = 1;
fa[2 * i + 1] = 2 * i + 1, siz[2 * i + 1] = 1;
cnt[i] = (b[i] > 0) + (t[i] > 0);
if (cnt[i] == 0) Free.insert(i);
}
for (int i = 1; i <= n; i++) {
int x = Loc[i][0], y = Loc[i][1];
if (x / 2 != y / 2) add_edge(x, y);
}
for (int i = 0; i < m; i++)
if (b[i] && t[i] && b[i] != t[i]) add_edge(2 * i, 2 * i + 1);
for (int i = 0; i < 2 * m; i++)
if (i == fa[i] && siz[i] > 1) red.push_back({{InCycle[i], TPCnt[i]}, i});
sort(red.begin(), red.end());
for (int i = 0; i < red.size(); i++) {
int idx = red[i].second;
if (!InCycle[idx])
solve_path(idx);
else
solve_cycle(idx);
}
if (moze == 0) {
cout << -1 << '\n';
return;
}
cout << sol.size() << endl;
for (auto pp : sol) cout << pp.first + 1 << " " << pp.second + 1 << '\n';
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:157:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for (int i = 0; i < red.size(); i++) {
| ~~^~~~~~~~~~~~
Main.cpp:166:5: error: return-statement with no value, in function returning 'int' [-fpermissive]
166 | return;
| ^~~~~~
