#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 assertTL(bool f) {
if (!f) {
while (1);
}
}
bool TL() {
return (double)clock() / CLOCKS_PER_SEC > 1.9;
}
void doOper(int i, int j) {
assertTL(i != j);
assertTL(a[i][0]);
int x = a[i][1] ? a[i][1] : a[i][0];
int from = a[i][1] ? 1 : 0;
assertTL(!a[j][1]);
assertTL(a[j][0] == 0 || a[j][0] == x);
int idx = -1;
fr (cur, 0, 1) {
if (pos[x][cur].fi == i && pos[x][cur].se == from) {
idx = cur;
break;
}
}
assertTL(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 {
assertTL(a[j][0]);
a[i][from] = 0;
a[j][1] = x;
pos[x][idx] = {j, 1};
}
opers.pb({i, j});
// fr (i, 1, m) {
// if (!a[i][0]) assertTL(emp.count(i));
// else assertTL(!emp.count(i));
//
// if (a[i][0]) assertTL(pos[a[i][0]][0] == mp(i, 0) || pos[a[i][0]][1] == mp(i, 0));
// if (a[i][1]) assertTL(pos[a[i][1]][0] == mp(i, 1) || pos[a[i][1]][1] == mp(i, 1));
// if (a[i][1]) {
// assertTL(a[i][0]);
// }
// }
}
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;
assert(n <= int(2e5));
assert(n >= 1);
assert(m <= int(2e5));
fr (i, 1, m) {
cin >> a[i][0] >> a[i][1];
assert(a[i][0] >= 0 && a[i][0] <= n);
assert(a[i][1] >= 0 && a[i][1] <= n);
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, n) {
assert(sz(pos[i]) == 2);
}
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 (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) {
fr (i, 1, m) {
if (a[i][0]) {
assert(a[i][0] == a[i][1]);
}
}
// assert(0);
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)) {
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;
}
assert(pos[i][0].se != pos[i][1].se);
}
bool ok = 0;
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) {
ok = 1;
if (j1 == 0) {
if (sz(emp)) {
int to = *emp.begin();
doOper(i1, to);
doOper(i2, i1);
found = 1;
break;
}
}
if (j2 == 0) {
if (sz(emp)) {
int to = *emp.begin();
doOper(i2, to);
doOper(i1, i2);
found = 1;
break;
}
}
}
}
assert(ok);
if (!found) {
bool have = 0;
fr (i, 1, m) {
fr (j, 1, m) {
if (i == j) continue;
if (!a[i][0]) continue;
if (a[j][1]) continue;
int x = a[i][1] ? a[i][1] : a[i][0];
if (!a[j][0] || a[j][0] == x) {
have = 1;
}
}
}
assert(!have);
cout << "-1\n";
return 0;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 6 |
Runtime error |
7 ms |
9940 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
16092 KB |
Output is correct |
| 2 |
Correct |
127 ms |
16260 KB |
Output is correct |
| 3 |
Correct |
91 ms |
15960 KB |
Output is correct |
| 4 |
Correct |
104 ms |
15924 KB |
Output is correct |
| 5 |
Correct |
128 ms |
16424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
10068 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
10068 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Runtime error |
8 ms |
10068 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 6 |
Runtime error |
7 ms |
9940 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
