#include <bits/stdc++.h>
using namespace std;
int N, M; bool vis[400005], rem[400005];
int P[400005], B[400005], T[400005];
priority_queue<pair<int, int>> pq;
vector<int> adj[400005], emp;
vector<pair<int, int>> res;
void add(vector<pair<int, int>>& C) {
reverse(C.begin(), C.end());
for(auto u : C) res.push_back(u);
C.clear();
}
int dfs(int v, int p, int t) {
if(v == t && p != -1) return v;
vis[v] = 1;
for(auto u : adj[v]) {
if(u == p || rem[u]) continue;
return dfs(u, v, t);
}
return v;
}
void caseA(int r) {
vector<pair<int, int>> C;
int p = r;
while(true) {
int v = -1, last = -1;
for(auto u : adj[r])
if(!rem[u] && u != p) v = u;
if(v == -1) break;
if(r % 2 == 1 && v % 2 == 1) {
if(emp.empty()) {
cout << -1;
exit(0);
}
res.push_back({r / 2, emp.back()});
res.push_back({v / 2, emp.back()});
emp.pop_back(); add(C);
if(last != -1) emp.push_back(last), last = -1;
}
else {
if((r / 2 != v / 2)) {
if(r & 1) C.push_back({r / 2, v / 2});
else C.push_back({v / 2, r / 2});
if(r % 2 == v % 2 && r % 2 == 0)
last = (C.back().first);
}
}
p = r, r = v;
}
add(C);
}
void caseB(int r) {
pair<int, int> K = {-1, -1};
int cur = 0, v = r, p = -1;
int X = -1, Y = -1;
while(true) {
int u = -1;
if((v & 1) == 1) X = v;
if(v == r) cur++;
if(cur == 2) break;
for(auto e : adj[v]) {
if(e != p) u = e;
}
if((v & 1) == 1 && (u & 1) == 1) {
K = {v, u}; break;
}
p = v, v = u;
}
if(emp.empty()) {
cout << -1; exit(0);
}
if(K != make_pair(-1, -1)) {
res.push_back({K.first / 2, emp.back()});
res.push_back({K.second / 2, emp.back()});
emp.pop_back(); rem[K.first] = rem[K.second] = 1;
for(auto u : adj[K.first]) {
if(u == K.second) continue;
caseA(u); break;
}
rem[K.first] = rem[K.second] = 0;
return;
}
for(auto u : adj[X])
if(u / 2 != X / 2) Y = u;
rem[X] = true;
res.push_back({X / 2, emp.back()});
adj[Y].push_back(emp.back() * 2);
adj[emp.back() * 2].push_back(Y);
int s = emp.back() * 2;
emp.pop_back(); caseA(s); rem[X] = false;
}
void solve(int v) {
int r = dfs(v, -1, v);
if(r == v) pq.push({1, r});
if(r != v) pq.push({2, r});
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> N >> M;
memset(P, -1, sizeof P);
for(int l = 0; l < M; l++) {
cin >> B[l] >> T[l];
if(B[l] == T[l] && B[l] > 0)
continue;
if(B[l] == 0) {
emp.push_back(l);
continue;
}
if(T[l] > 0)
adj[l * 2].push_back(l * 2 + 1),
adj[l * 2 + 1].push_back(l * 2);
if(P[B[l]] != -1)
adj[l * 2].push_back(P[B[l]]),
adj[P[B[l]]].push_back(l * 2);
if(P[T[l]] != -1)
adj[l * 2 + 1].push_back(P[T[l]]),
adj[P[T[l]]].push_back(l * 2 + 1);
P[B[l]] = l * 2;
if(T[l] > 0) P[T[l]] = l * 2 + 1;
}
for(int l = 0; l < M * 2; l++) {
if(vis[l] || adj[l].empty()) continue;
solve(l);
}
while(!pq.empty()) {
int v = pq.top().second, t = pq.top().first;
if(t == 1) caseB(v);
if(t == 2) caseA(v);
pq.pop();
}
cout << res.size() << "\n";
for(auto u : res) cout << ++u.first << " " << ++u.second << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
112 ms |
21140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
