#include <bits/stdc++.h>
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
using namespace std;
mt19937_64 rng(228);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
bool umn(T& a, T b) {
return a > b ? (a = b, 1) : 0;
}
template <typename T>
bool umx(T& a, T b) {
return a < b ? (a = b, 1) : 0;
}
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
const int N = 2e5 + 5;
int n, m;
int a[N][2];
ve<pii> opers;
ve<pii> pos[N];
set<int> emp;
void doOper(int i, int j) {
// cout << "MAKE OPER " << i << " " << j << "\n" << flush;
assert(i != j);
assert(a[i][0]);
int x = a[i][1] ? a[i][1] : a[i][0];
// cout << "x: " << x << "\n";
int from = a[i][1] ? 1 : 0;
assert(!a[j][1]);
assert(a[j][0] == 0 || a[j][0] == x);
// cout << i << " " << from << "\n";
int idx = -1;
fr (cur, 0, 1) {
if (pos[x][cur].fi == i && pos[x][cur].se == from) {
idx = cur;
break;
}
}
assert(idx != -1);
if (from == 0) {
emp.insert(i);
}
if (a[j][0] == 0) {
a[i][from] = 0;
a[j][0] = x;
pos[x][idx] = {j, 0};
emp.erase(j);
} else {
assert(a[j][0]);
a[i][from] = 0;
a[j][1] = x;
pos[x][idx] = {j, 1};
}
opers.pb({i, j});
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(0);
cin.tie(0);
#endif
cin >> n >> m;
fr (i, 1, m) {
cin >> a[i][0] >> a[i][1];
if (a[i][0]) {
pos[a[i][0]].pb({i, 0});
}
if (a[i][1]) {
pos[a[i][1]].pb({i, 1});
}
}
fr (i, 1, m) {
if (!a[i][0]) {
emp.insert(i);
}
}
while (1) {
bool found = 0;
int cnt = 0;
fr (i, 1, n) {
if (pos[i][0].fi == pos[i][1].fi) {
cnt++;
continue;
}
int i1 = pos[i][0].fi;
int j1 = pos[i][0].se;
int i2 = pos[i][1].fi;
int j2 = pos[i][1].se;
// if (i == 2) {
// cout << "YEP\n";
// cout << i1 << " " << j1 << " " << i2 << " " << j2 << "\n";
// }
if (j1 == 1 || !a[i1][1]) {
if (j2 == 0 && !a[i2][1]) {
doOper(i1, i2);
found = 1;
continue;
}
}
if (j2 == 1 || !a[i2][1]) {
if (j1 == 0 && !a[i1][1]) {
doOper(i2, i1);
found = 1;
}
}
}
if (cnt == n) {
cout << sz(opers) << "\n";
fe (x, opers) {
cout << x.fi << " " << x.se << "\n";
}
return 0;
}
if (found) {
continue;
}
fr (i, 1, n) {
if (pos[i][0].fi == pos[i][1].fi) {
continue;
}
int i1 = pos[i][0].fi;
int j1 = pos[i][0].se;
int i2 = pos[i][1].fi;
int j2 = pos[i][1].se;
if (j1 == 1 && j2 == 1) {
if (!sz(emp)) {
cout << "-1\n";
return 0;
}
int to = *emp.begin();
doOper(i1, to);
doOper(i2, to);
found = 1;
}
}
if (found) {
continue;
}
// cout << "YEP HERE\n";
fr (i, 1, n) {
if (pos[i][0].fi == pos[i][1].fi) {
continue;
}
int i1 = pos[i][0].fi;
int j1 = pos[i][0].se;
int i2 = pos[i][1].fi;
int j2 = pos[i][1].se;
if (j1 != j2) {
if (j1 == 0) {
if (!sz(emp)) {
cout << "-1\n";
return 0;
}
int to = *emp.begin();
doOper(i1, to);
found = 1;
break;
}
if (j2 == 0) {
if (!sz(emp)) {
cout << "-1\n";
return 0;
}
int to = *emp.begin();
doOper(i2, to);
found = 1;
break;
}
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5028 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5028 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
5020 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
17464 KB |
Output is correct |
| 2 |
Correct |
131 ms |
17612 KB |
Output is correct |
| 3 |
Correct |
89 ms |
17060 KB |
Output is correct |
| 4 |
Correct |
96 ms |
16928 KB |
Output is correct |
| 5 |
Correct |
132 ms |
17648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5028 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5028 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
5020 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
119 ms |
17464 KB |
Output is correct |
| 12 |
Correct |
131 ms |
17612 KB |
Output is correct |
| 13 |
Correct |
89 ms |
17060 KB |
Output is correct |
| 14 |
Correct |
96 ms |
16928 KB |
Output is correct |
| 15 |
Correct |
132 ms |
17648 KB |
Output is correct |
| 16 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
