#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define int long long
const int inf=1e18;
int dfs(int v, map<int, vector<int> >& adi, map<int, bool>& vis){
cout << v << "\n";
if(vis[v]) return 0;
vis[v]=true;
int cnt=1;
for(auto u: adi[v]){
cnt+=dfs(u, adi, vis);
}
return cnt;
}
bool connected(int n, int start, map<int, vector<int> >& adi){
map<int, bool> vis;
return dfs(start, adi, vis)==n;
}
int plan_roller_coaster(vector<int32_t> s, vector<int32_t> t){
int n=s.size();
map<int, vector<int> > adi;
vector<pair<int, int> > time;
for(int i=0; i<n; i++){
adi[s[i]].push_back(t[i]);
time.push_back({s[i], 1});
time.push_back({t[i], -1});
}
sort(time.begin(), time.end());
bool pos=true;
int sum=-1;
int dif=1;
for(int i=0; i<(int)time.size(); i++){
if(0<i && time[i-1].first!=time[i].first){
dif++;
}
sum+=time[i].second;
if(sum>0) pos=false;
if(sum<0 && i+1<(int)time.size()){
adi[time[i].first].push_back(time[i+1].first);
}
}
//cout << pos << " " << dif << "\n";
if(pos && connected(dif, s[0], adi)){
return 0;
}
return 1;
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int32_t> s(n);
vector<int32_t> t(n);
for(int i=0; i<n; i++){
cin >> s[i];
}
for(int i=0; i<n; i++){
cin >> t[i];
}
cout << plan_roller_coaster(s, t) << "\n";
}*/
