#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
int main() {
cin.tie(0);
int n, m;
cin >> n >> m;
vector<set<int> > L(n), G(n);
vi A(2 * m, -1), P(2 * n, -1);
set<int> LinLib;
for(int i = 0; i < 2 * m; ++i) {
int v;
cin >> v;
if(!v) continue;
--v;
v *= 2;
if(P[v] != -1) ++v;
P[v] = i;
A[i] = v;
}
//set<int> Scoase;
vi InDeg(n, 0), OutDeg(n, 0);
for(int i = 0; i < m; ++i) {
if(A[2 * i] == -1) LinLib.insert(i);
if(A[2 * i + 1] != -1) {
if(A[2 * i] == A[2 * i + 1]) continue;
L[A[2 * i] / 2].insert(A[2 * i + 1] / 2);
L[A[2 * i + 1] / 2].insert(A[2 * i] / 2);
++OutDeg[A[2 * i] / 2];
++InDeg[A[2 * i + 1] / 2];
}
}
set<int> S[3][3]; /// culori dupa indeg/ outdeg
for(int i = 0; i < n; ++i)
S[InDeg[i]][OutDeg[i]].insert(i);
vector<vi> LMono, LBi;
vector<vi> Cicluri;
vi viz(n, 0);
function<int(int, int)> dfs0 = [&](int u, int p) {
if(viz[u] == 1)
return u;
viz[u] = 1;
for(auto it : L[u])
if(it != p) return dfs0(it, u);
for(auto it : G[u])
if(it != p) return dfs0(it, u);
return u;
};
function<void(int, int, bool&, int&, vi&)> dfscomp = [&](int u, int p, bool &cyc, int& dir, vi &comp) {
if(viz[u] == 2) {
cyc = 1;
return;
}
viz[u] = 2;
dir = max(dir, InDeg[u]);
comp.push_back(u);
for(auto it : L[u])
if(it != p) {
dfscomp(it, u, cyc, dir, comp);
}
for(auto it : G[u])
if(it != p) {
dfscomp(it, u, cyc, dir, comp);
}
};
for(int i = 0; i < n; ++i) {
if(!viz[i]) {
int u = dfs0(i, -1), dir = 0;
bool cyc = 0;
vi comp;
dfscomp(u, -1, cyc, dir, comp);
if(cyc) Cicluri.push_back(comp);
else {
if(dir == 2) LBi.push_back(comp);
else LMono.push_back(comp);
}
}
}
int ok = 1;
vector<ii> Sol;
auto move = [&](int from, int to) {
Sol.push_back({from, to});
int pf = 2 * from, pdest = 2 * to;
if(A[pf + 1] != -1) {
L[A[pf] / 2].erase(A[pf + 1] / 2);
G[A[pf + 1] / 2].erase(A[pf] / 2);
--OutDeg[A[pf] / 2];
--InDeg[A[pf + 1] / 2];
++pf;
} else LinLib.insert(from);
if(A[pdest] != -1) {
L[A[pdest] / 2].insert(A[pf] / 2);
G[A[pf] / 2].insert(A[pdest] / 2);
++InDeg[A[pf] / 2];
++OutDeg[A[pdest] / 2];
++pdest;
} else LinLib.erase(to);
A[pdest] = A[pf];
A[pf] = -1;
P[A[pdest]] = pdest;
};
auto scotdeg2 = [&](int u) {
int liber;
if(LinLib.empty()) {
cout << "-1\n";
exit(0);
}
liber = *LinLib.begin();
move(P[2 * u] / 2, liber);
move(P[2 * u + 1] / 2, liber);
};
auto solveSir = [&](vi S) {
if(S.empty()) return;
auto singur = [&](int u) {
if(P[2 * u] / 2 != P[2 * u + 1] / 2)
move(P[2 * u] / 2, P[2 * u + 1] / 2);
};
if(S.size() == 1) {
int u = S[0];
singur(u);
return;
}
deque<int> D;
for(auto it : S) D.push_back(it);
auto scoate = [&](int u) {
int a = P[2 * u], b = P[2 * u + 1];
if(b & 1) swap(a, b);
move(a / 2, b / 2);
};
while(!D.empty()) {
if(InDeg[D.back()] == 0 && OutDeg[D.back()] == 0) {
singur(D.back());
D.pop_back();
continue;
}
if(InDeg[D.front()] == 1) {
scoate(D.front());
D.pop_front();
continue;
}
if(InDeg[D.back()] == 1) {
scoate(D.back());
D.pop_back();
continue;
}
int u = D.back(), p = -1;
vi Acum;
while(InDeg[u] != 2) {
Acum.push_back(D.back());
D.pop_back();
u = D.back();
}
//il scot pe u acum
scotdeg2(u);
D.pop_back();
reverse(Acum.begin(), Acum.end());
for(int i = 0; i + 1 < Acum.size(); ++i)
scoate(Acum[i]);
singur(Acum.back());
}
};
auto solveCyc = [&](vi C) {
deque<int> D;
for(auto it : C)
D.push_back(it);
for(int i = 0; i < n; ++i) {
if(InDeg[D.back()] == 2) {
scotdeg2(D.back());
D.pop_back();
vi S;
for(auto it : D) S.push_back(it);
solveSir(S);
return;
}
D.push_front(D.back());
D.pop_back();
}
///e full ciclic
int u = D.back(), a = P[2 * u], b = P[2 * u + 1];
if(b & 1) swap(a, b);
int liber;
if(LinLib.empty()) {
cout << "-1\n";
exit(0);
}
liber = *LinLib.begin();
int urm = A[a - 1];
move(a / 2, liber);
if(D.front() == urm) {
D.push_back(D.front());
D.pop_front();
}
else {
D.push_front(D.back());
D.pop_back();
}
vi S;
for(auto it : D) S.push_back(it);
solveSir(S);
return;
};
for(auto it : LMono) solveSir(it);
for(auto it : LBi) solveSir(it);
for(auto it : Cicluri) solveCyc(it);
if(!ok) {
cout << "-1\n";
return 0;
}
cout << Sol.size() << "\n";
for(auto [a, b] : Sol)
cout << a + 1 << " " << b + 1 << "\n";
return 0;
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:173:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(int i = 0; i + 1 < Acum.size(); ++i)
| ~~~~~~^~~~~~~~~~~~~
Main.cpp:161:31: warning: unused variable 'p' [-Wunused-variable]
161 | int u = D.back(), p = -1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
32788 KB |
Output is correct |
| 2 |
Correct |
200 ms |
38152 KB |
Output is correct |
| 3 |
Correct |
103 ms |
27144 KB |
Output is correct |
| 4 |
Correct |
130 ms |
25860 KB |
Output is correct |
| 5 |
Correct |
148 ms |
37896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
