#include<bits/stdc++.h>
using namespace std;
#include "railroad.h"
const int N = 4e5+37;
priority_queue<array<int, 2>> adj[N];
array<int, 2> st[N*4];
void update(int v, int l, int r,int pos, array<int, 2> val){
if(l==r) st[v] = val;
else if(l<r){
int mid = (r+l)/2;
if(pos <= mid) update(v*2, l, mid, pos, val);
else update(v*2+1, mid+1, r, pos, val);
st[v] = min(st[v*2], st[v*2+1]);
}
}
array<int, 2> get(int v, int l, int r,int tl,int tr){
if(l>r || tr < l || r < tl) return {N, N};
else if(l>=tl && r<= tr) return st[v];
else{
int mid = (r+l)/2;
return min(get(v*2, l, mid, tl, tr),
get(v*2+1, mid+1, r, tl, tr));
}
}
void update2(int v, int l, int r,int pos, array<int, 2> val){
if(l==r) st[v] = val;
else if(l<r){
int mid = (r+l)/2;
if(pos <= mid) update2(v*2, l, mid, pos, val);
else update2(v*2+1, mid+1, r, pos, val);
st[v] = max(st[v*2], st[v*2+1]);
}
}
array<int, 2> get2(int v, int l, int r,int tl,int tr){
if(l>r || tr < l || r < tl) return {-1, -1};
else if(l>=tl && r<= tr) return st[v];
else{
int mid = (r+l)/2;
return max(get2(v*2, l, mid, tl, tr),
get2(v*2+1, mid+1, r, tl, tr));
}
}
void f(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
map<int, int> mp;
vector<int> j;
for(auto i: s) j.push_back(i);
for(auto i: t) j.push_back(i);
sort(j.begin(), j.end());
int cur=0;
for(auto i:j){
if(mp.count(i)) continue;
mp[i]=cur; cur++;
}
for(auto &i: s) i=mp[i];
for(auto &i: t) i=mp[i];
int n=s.size();
vector<array<int, 2>> q(n);
for(int i=0; i<n*4*2+37; i++){
st[i]={N, N};
}
for(int i=0; i<n; i++){
q[i]={s[i], t[i]};
}
sort(s.begin(), s.end());
sort(q.begin(), q.end());
vector<int> e(n), pe(n);
for(int i=0; i<n; i++){
e[i] = q[i][1];
pe[i] = q[i][0];
adj[pe[i]].push({(int)-e[i], i});
}
for(int i=0; i<=n; i++){
if(adj[i].size()){
update(1, 0, 2*n, i, {-adj[i].top()[0], adj[i].top()[1]});
}
}
vector<int> vis(n+1);
queue<int> qu;
qu.push(0);
while(qu.size()){
int f=qu.front(); qu.pop();
//cout<<f<<"\n";
if(f==N) break;
vis[f] =1;
int c=adj[pe[f]].size();
while(adj[pe[f]].size()&&vis[adj[pe[f]].top()[1]]){
adj[pe[f]].pop();
}
if(adj[pe[f]].size()){
update(1, 0, 2*n, pe[f], {-adj[pe[f]].top()[0], adj[pe[f]].top()[1]});
}
else if(c){
update(1, 0, 2*n, pe[f], {N, N});
}
auto k=get(1, 0, 2*n, e[f], n)[1];
qu.push(k);
}
for(int i=0; i<n; i++){
adj[i]=priority_queue<array<int, 2>>();
}
for(int i=0; i<n*4*2+37; i++){
st[i]={-1, -1};
}
for(int i=0; i<n; i++){
if(vis[i]) continue;
adj[e[i]].push({(int)pe[i], i});
}
qu.push(0);
for(int i=0; i<=n; i++){
if(adj[i].size()){
update2(1, 0, n*2, i, {adj[i].top()});
}
}
while(qu.size()){
int f=qu.front(); qu.pop();
if(f==-1) break;
vis[f] =1;
int c=adj[e[f]].size();
while(adj[e[f]].size()&&vis[adj[e[f]].top()[1]]){
adj[e[f]].pop();
}
if(adj[e[f]].size()){
update2(1, 0, n*2, e[f], adj[e[f]].top());
}
else if(c){
update2(1, 0, n*2, e[f], {-1, -1});
}
auto k=get2(1, 0, n*2, 0, pe[f])[1];
qu.push(k);
}
for(int i=0; i<n; i++) if(vis[i]==0) return 1;
return 0;
}
/*
int main() {
f();
int n;
assert(1 == scanf("%d", &n));
std::vector<int> s(n), t(n);
for (int i = 0; i < n; ++i)
assert(2 == scanf("%d%d", &s[i], &t[i]));
long long ans = plan_roller_coaster(s, t);
printf("%lld\n", ans);
return 0;
}*/
