#include "railroad.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
const int MAXN = 4e5+5;
ll inf = 1e18;
int n;
vector<int> s, t;
ll pos_all[MAXN];
vector<int> edges[MAXN], rev[MAXN];
vector<pii> Eedges[MAXN], Erev[MAXN];
vector<pii> all;
int used[MAXN];
ll plan_roller_coaster(vector<int> sk, vector<int> tk) {
s = sk, t = tk;
n = s.size();
for(int i=0;i<n;i++){
all.push_back({s[i], i});
all.push_back({t[i], i+n});
pos_all[i] = s[i];
pos_all[i+n] = t[i];
edges[i].push_back(i+n);
rev[i+n].push_back(i);
}
sort(all.begin(), all.end());
auto [no_need_1, fff] = all[0];
auto [no_need_2, sss] = all[(int)all.size()-1];
edges[sss].push_back(fff);
rev[fff].push_back(sss);
{ /// Making A = B
map<int,int> getting, bgetting;
int A=0, B=0;
for(int i=0;i<(int)all.size()-1;i++){
int ind1 = all[i].second;
int ind2 = all[i+1].second;
for(auto x : edges[ind1]){
if(getting.count(x)){
getting[x]--;
B--;
}else {
if(pos_all[ind1] <= pos_all[x]){
A++;
bgetting[ind1]++;
}else assert(false);
}
}
for(auto x : rev[ind1]){
if(bgetting.count(x)){
bgetting[x]--;
A--;
}else {
if(pos_all[ind1] <= pos_all[x]){
B++;
getting[ind1]++;
}else assert(false);
}
}
for(auto [x, y] : Erev[ind1]){
if(bgetting.count(x)){
int mn = min(bgetting[x],y);
bgetting[x]-=mn;
A-=mn;
}
}
//~ cout << A << '-' << B << '\n';
if(A > B)return 1000000000;
if(A < B){
Eedges[ind1].push_back({ind2,B-A});
Erev[ind2].push_back({ind1,B-A});
bgetting[ind1] += B-A;
A = B;
}
}
}
/// check for connectivity
queue<int> q;
q.push(0);
used[0] = true;
while(!q.empty()){
int u = q.front();q.pop();
for(auto v : edges[u]){
if(!used[v]){
q.push(v);used[v] = true;
}
}for(auto [v,c] : Eedges[u]){
if(!used[v]){
q.push(v);used[v] = true;
}
}
}
for(int i=0;i<n*2;i++){
if(!used[i])return 987654321;
}
memset(used, 0, sizeof used);
q.push(0);
used[0] = true;
while(!q.empty()){
int u = q.front();q.pop();
for(auto v : rev[u]){
if(!used[v]){
q.push(v);used[v] = true;
}
}for(auto [v,c] : Erev[u]){
if(!used[v]){
q.push(v);used[v] = true;
}
}
}
for(int i=0;i<n*2;i++){
if(!used[i])return 123456789;
}
/// now we need to start from arbitrary node and check for eulerian circuit
for(int i=0;i<n;i++){
int s1 = edges[i].size(), s2 = rev[i].size();
for(auto [u, c] : Eedges[i])s1 += c;
for(auto [u, c] : Erev[i])s2 += c;
}
//~ int now = 0;
//~ while(!edges[now].empty() || !Eedges[now].empty()){
//~ if(!edges[now].empty()){
//~ int t = edges[now].back();
//~ edges[now].pop_back();
//~ now = t;
//~ }else {
//~ auto &[t, y] = Eedges[now].back();
//~ y--;
//~ if(y == 0)Eedges[now].pop_back();
//~ now = t;
//~ }
//~ }
//~ for(int i=0;i<n*2;i++){
//~ if(!edges[i].empty() || !Eedges[i].empty())return 999999999;
//~ }
return 0;
}
