#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
lint D[1<<16][16];
int v[200002];
int line[200002],to[200002],rev[200002],sT[200002],num[200002],col;
void dfs(int p)
{
v[p]=col;
if(!v[sT[to[p]]])dfs(sT[to[p]]);
}
lint plan_roller_coaster(vector<int> s, vector<int> t) {
int n = (int) s.size();
int ch=0;
vector<pii>S;
vector<pii>T;
for(int i=0;i<n;i++)S.push_back({s[i],i});
for(int i=0;i<n;i++)T.push_back({t[i],i});
S.push_back({1e9+1,n});T.push_back({0,n});
for(int i=0;i<n;i++)
{
assert(t[i]>=1 && t[i]<=1e9);
assert(s[i]>=1 && s[i]<=1e9);
}
sort(S.begin(),S.end());
sort(T.begin(),T.end());
for(int i=0;i<=n;i++)num[T[i].second]=i;
int j=0;
for(int i=0;i<=n;i++)
{
while(j<=n && T[i].first>S[j].first)j++;
line[i]=j;
if(j>i)
{
return 1;
}
to[i]=i;rev[i]=i;
sT[i]=num[S[i].second];
}
col=0;
for(int i=0;i<=n;i++)
{
if(!v[i])
{
col++;
dfs(i);
}
}
for(int i=0;i<=n;i++)
{
if(v[i]!=1 && line[i]==i)return 1;
}
return ch;
}
