#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int n, m, a, b, e, kol, kolg, jed, sol;
vector<int> v[200005];
int g[200005];
int bio[200005];
vector<int> pr;
int gdje[200005][5];
vector<int> smj[200005];
int ideu[200005];
set< pair<int, pair<int, int> > > s;
set< pair<int, pair<int, int> > > :: iterator it;
pair<int, int> pos[200005];
vector< pair<int, int> > out;
vector< pair<int, int> > tren;
int sam[200005];
int znak[200005];
int dalje[200005];
vector< pair< int, pair<int, int> > > svi;
vector<int> pravi[200005];
void dfs(int x) {
if (v[x].size() == 1) jed = 1;
bio[x] = 1;
kol++;
if (g[x] == 2) {
kolg++;
s.insert({0, {1, x}});
}
else {
s.insert({ideu[x], {0, x}});
}
for (int i = 0; i < v[x].size(); i++) {
if (bio[v[x][i]] == 0) dfs(v[x][i]);
}
}
void rek(int x) {
bio[x] = 1;
if (gdje[pos[x].X][0] == x && gdje[pos[x].Y][0] == x) tren.push_back({x, 1});
else if (gdje[pos[x].X][1] == x && gdje[pos[x].Y][1] == x) tren.push_back({x, -1});
else tren.push_back({x, 0});
for (int i = 0; i < v[x].size(); i++) {
if (bio[v[x][i]] == 0) rek(v[x][i]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) pos[i] = {-1, -1};
for (int i = 0; i < m; i++) {
cin >> a >> b;
gdje[i][0] = a;
gdje[i][1] = b;
if (pos[a].X == -1) pos[a].X = i;
else pos[a].Y = i;
if (pos[b].X == -1) pos[b].X = i;
else pos[b].Y = i;
if (a == 0 && b == 0) {
e++;
pr.push_back(i);
}
else if (a != b && a > 0 && b > 0) {
smj[a].push_back(b);
ideu[a]++;
v[a].push_back(b);
v[b].push_back(a);
g[b]++;
pravi[b].push_back(a);
}
else if (b == 0) {
if (sam[a] == 0) sam[a] = i+1;
else {
sol++;
e++;
out.push_back({i, sam[a]-1});
pr.push_back(i);
}
}
}
for (int i = 1; i <= n; i++) {
if (bio[i] == 0 && (int)v[i].size() > 0) {
kol = 0, kolg = 0, jed = 0;
s.clear();
dfs(i);
svi.push_back({1-jed, {kolg, i}});
sol += kol+max(1, kolg);
}
}
sort(svi.begin(), svi.end());
memset(bio, 0, sizeof bio);
for (int i = 0; i < svi.size(); i++) {
if (svi[i].X == 0) {
if (svi[i].Y.X > 0 && e < 1) {
cout << -1;
return 0;
}
if (svi[i].Y.X == 0) sol--;
e++;
}
else {
if ((svi[i].Y.X > 1 && e < 2) || e < 1) {
cout << -1;
return 0;
}
}
tren.clear();
rek(svi[i].Y.Y);
int raz = 0;
for (int j = 0; j < tren.size(); j++) {
if (tren[j].Y != 0) raz++;
}
if (raz == 0 && svi[i].X == 1) {
int wh = pos[svi[i].Y.Y].X;
if (gdje[wh][0] != svi[i].Y.Y) wh = pos[svi[i].Y.Y].Y;
out.push_back({wh, pr.back()});
pravi[ smj[svi[i].Y.Y][0] ].clear();
if (pos[ smj[svi[i].Y.Y][0] ].X == wh) pos[ smj[svi[i].Y.Y][0] ].X = pr.back();
else pos[ smj[svi[i].Y.Y][0] ].Y = pr.back();
smj[svi[i].Y.Y].clear();
while (1) {
}
}
s.clear();
for (int j = 0; j < tren.size(); j++) {
znak[tren[j].X] = 1-tren[j].Y;
dalje[tren[j].X] = (int)smj[tren[j].X].size();
s.insert({(int)smj[tren[j].X].size(), {1-tren[j].Y, tren[j].X}});
}
for (int abc = 0; abc < tren.size(); abc++) {
int novi = -1, w = 0;
pair<int, pair<int, int> > broj = *s.begin();
s.erase(s.begin());
novi = broj.Y.Y;
w = 1 - broj.Y.X;
for (int j = 0; j < pravi[novi].size(); j++) {
int susjed = pravi[novi][j];
if (s.find({dalje[susjed], {znak[susjed], susjed}}) != s.end()) {
s.erase({dalje[susjed], {znak[susjed], susjed}});
dalje[susjed]--;
s.insert({dalje[susjed], {znak[susjed], susjed}});
}
else {
while (1) {
}
}
}
/*for (int j = 0; j < tren.size(); j++) {
if (bio[tren[j].X] == 2) continue;
int koll = 0, k2 = 0;
if (smj[tren[j].X].size() > 0 && bio[smj[tren[j].X][0]] != 2) {
koll++;
if (g[smj[tren[j].X][0]] == 2) k2++;
}
if (smj[tren[j].X].size() > 1 && bio[smj[tren[j].X][1]] != 2) {
koll++;
if (g[smj[tren[j].X][1]] == 2) k2++;
}
if (koll == 0 && tren[j].Y >= 0 && k2 == 0) {
novi = tren[j].X;
w = tren[j].Y;
break;
}
if (koll == 0) {
novi = tren[j].X;
w = tren[j].Y;
}
}
bio[novi] = 2;*/
if (w == -1) {
out.push_back({pos[novi].X, pr.back()});
out.push_back({pos[novi].Y, pr.back()});
pr.pop_back();
}
else if (w == 1) {
out.push_back({pos[novi].X, pos[novi].Y});
pr.push_back(pos[novi].X);
}
else {
if (gdje[ pos[novi].X ][0] == novi) out.push_back({pos[novi].Y, pos[novi].X});
else out.push_back({pos[novi].X, pos[novi].Y});
}
}
}
cout << sol << "\n";
for (int i = 0; i < out.size(); i++) cout << out[i].X+1 << " " << out[i].Y+1 << "\n";
return 0;
}
Compilation message
Main.cpp: In function 'void dfs(int)':
Main.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i = 0; i < v[x].size(); i++) {
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'void rek(int)':
Main.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i < v[x].size(); i++) {
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int i = 0; i < svi.size(); i++) {
| ~~^~~~~~~~~~~~
Main.cpp:130:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for (int j = 0; j < tren.size(); j++) {
| ~~^~~~~~~~~~~~~
Main.cpp:150:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (int j = 0; j < tren.size(); j++) {
| ~~^~~~~~~~~~~~~
Main.cpp:156:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for (int abc = 0; abc < tren.size(); abc++) {
| ~~~~^~~~~~~~~~~~~
Main.cpp:164:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for (int j = 0; j < pravi[novi].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:221:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
221 | for (int i = 0; i < out.size(); i++) cout << out[i].X+1 << " " << out[i].Y+1 << "\n";
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15188 KB |
Output is correct |
| 2 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 3 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 4 |
Execution timed out |
2063 ms |
15188 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
27548 KB |
Output is correct |
| 2 |
Correct |
155 ms |
29812 KB |
Output is correct |
| 3 |
Correct |
64 ms |
24848 KB |
Output is correct |
| 4 |
Correct |
60 ms |
24276 KB |
Output is correct |
| 5 |
Correct |
126 ms |
29676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2072 ms |
15188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2072 ms |
15188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
15316 KB |
Output is correct |
| 2 |
Correct |
9 ms |
15400 KB |
Output is correct |
| 3 |
Correct |
11 ms |
15316 KB |
Output is correct |
| 4 |
Execution timed out |
2072 ms |
15188 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15188 KB |
Output is correct |
| 2 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 3 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 4 |
Execution timed out |
2063 ms |
15188 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
