#include "bits/stdc++.h"
using namespace std;
const int MAXN = 200010;
set<int> adj[MAXN];
int N, M;
int in[MAXN];
stack<int> st[MAXN];
queue<pair<int, int> > q;
set<int> vacant;
multiset<pair<int, char> > pos[MAXN];
void op(int x, int y) {
assert(min(x, y) != -1);
if(st[x].empty()) {
cout << "error_st["<<x<<"]_is_empty\n";
while(1) {}
exit(0);
}
int tar = st[x].top();
pos[tar].erase(pos[tar].lower_bound({x, 't'}));
pos[tar].insert({y, 't'});
if(st[y].size()) {
pos[st[y].top()].erase(pos[st[y].top()].lower_bound({y, 't'}));
pos[st[y].top()].insert({y, 'b'});
}
if(st[y].size()) in[st[y].top()]++;
st[y].push(st[x].top());
st[x].pop();
if(st[x].size()) in[st[x].top()]--;
if(st[x].size()) {
pos[st[x].top()].erase(pos[st[x].top()].lower_bound({x, 'b'}));
pos[st[x].top()].insert({x, 't'});
}
if(st[x].empty()) {
vacant.insert(x);
}
if(vacant.count(y)) {
vacant.erase(y);
}
if(st[y].size() > 2) {
cout << "error_st["<<y<<"]_has_more_than_2_cars\n";
while(1) {}
exit(0);
}
q.push({x, y});
}
bool vis[MAXN];
stack<int> topo;
void dfs(int node) {
vis[node] = 1;
for(int x: adj[node]) {
if(!vis[x]) dfs(x);
}
topo.push(node);
}
int find_top(int x) {
for(pair<int, char> p: pos[x]) {
if(p.second == 't') return p.first;
}
return -1;
}
int find_bottom(int x) {
for(pair<int, char> p: pos[x]) {
if(p.second == 'b') return p.first;
}
return -1;
}
int find_empty_pile() {
return (vacant.size() ? (*vacant.begin()) : -1);
}
int freq[MAXN];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
bool done = 1;
for(int i=1; i<=M; i++) {
int b, t;
cin >> b >> t;
freq[b]++;
freq[t]++;
if(b != 0) {
pos[b].insert({i, (t == 0 ? 't' : 'b')});
}
if(t != 0) {
pos[t].insert({i, 't'});
}
if(b == 0) vacant.insert(i);
done &= (b == t);
if(t != 0) {
adj[t].insert(b);
in[b]++;
}
if(b != 0) {
st[i].push(b);
if(t != 0) {
st[i].push(t);
}
}
}
if(done) return cout << "0\n", 0;
if(N == M) return cout << "-1\n", 0;
for(int i=1; i<=N; i++) {
if(freq[i] != 2) return cout << "-1\n", 0;
}
for(int i=1; i<=N; i++) {
if(!vis[i]) {
dfs(i);
}
}
for(int i=1; i<=N; i++) vis[i] = 0;
while(topo.size()) {
int tt = topo.top(); topo.pop();
if(in[tt]) { // permutation
if(find_top(tt) == find_bottom(tt)) continue;
int fep = find_empty_pile();
if(fep == -1) return cout << "-1\n", 0;
int cur = find_top(tt);
int tar = fep;
while(1) {
if(cur == tar) break;
op(cur, tar);
if(cur == fep) break;
tar = cur;
int be = st[cur].top(); // bottom element guaranteed
cur = find_top(be);
}
if(cur == tar) {
int f = (*pos[st[cur].top()].begin()).first;
int t = (*pos[st[cur].top()].rbegin()).first;
op(f, t);
}
}
else { // no in-deg
int from, to = -1;
for(pair<int, char> p : pos[tt]) {
if(st[p.first].size() == 1) to = p.first;
}
if(to != -1) {
for(pair<int, char> p : pos[tt]) {
if(to != p.first) from = p.first;
}
}
else {
int fep = find_empty_pile();
if(fep == -1) return cout << "-1\n", 0;
from = -1, to = fep;
}
vector<int> bruh;
for(pair<int, char> p : pos[tt]) {
bruh.push_back(p.first);
}
for(int x: bruh) {
if(from == -1 || from == x) op(x, to);
}
}
}
cout << q.size() << '\n';
while(q.size()) {
cout << q.front().first << ' ' << q.front().second << '\n'; q.pop();
}
}
/*
g++ parking.cpp -std=c++17 -o parking
g++ gen.cpp -std=c++17 -o gen
for ((i=1; ; ++i)); do
./gen $i > in.txt
./parking < in.txt
done
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:153:31: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
153 | if(from == -1 || from == x) op(x, to);
| ~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
86 ms |
153640 KB |
Output is correct |
| 2 |
Correct |
85 ms |
153656 KB |
Output is correct |
| 3 |
Correct |
85 ms |
153676 KB |
Output is correct |
| 4 |
Execution timed out |
2099 ms |
153712 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
317 ms |
170444 KB |
Output is correct |
| 2 |
Correct |
343 ms |
172704 KB |
Output is correct |
| 3 |
Correct |
282 ms |
168140 KB |
Output is correct |
| 4 |
Correct |
234 ms |
167556 KB |
Output is correct |
| 5 |
Correct |
339 ms |
172736 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
86 ms |
153852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
86 ms |
153852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
96 ms |
153876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
86 ms |
153640 KB |
Output is correct |
| 2 |
Correct |
85 ms |
153656 KB |
Output is correct |
| 3 |
Correct |
85 ms |
153676 KB |
Output is correct |
| 4 |
Execution timed out |
2099 ms |
153712 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
