#include "stations.h"
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;
const int maxn = 1005;
int tin[maxn], tout[maxn], tr=-1;
vector<int> edges[maxn];
void dfs(int c, int p)
{
tin[c]=++tr;
for (int i : edges[c])
if (i!=p)
dfs(i,c);
tout[c]=tr;
}
std::vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
tr=-1;
for (int i=0;i<n;++i)
edges[i].clear();
for (int i=0;i<n-1;++i)
{
edges[u[i]].push_back(v[i]);
edges[v[i]].push_back(u[i]);
}
dfs(0,-1);
for (int i = 0; i < n; i++) {
labels[i] = tin[i]*1000+tout[i];
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c)
{
/**cout<<s<<" "<<t<<"!\n";
for (int i : c)
cout<<i<<" ";
cout<<"\n";**/
if ((s/1000)<=(t/1000)&&(t%1000)<=(s%1000))
{
for (int i : c)
{
if ((i/1000)<=(t/1000)&&(t%1000)<=(i%1000)&&(s/1000)<=(i/1000)&&(i%1000)<=(s%1000))
return i;
}
}
else
{
for (int i : c)
{
if ((i/1000)<=(s/1000)&&(s%1000)<=(i%1000))
return i;
}
}
return 3141;
}
/**
int main()
{
int n,k,x,y,q;
cin>>n>>k;
vector<int> a,b,v;
for (int i=1;i<n;++i)
{
cin>>x>>y;
a.push_back(x);
b.push_back(y);
}
vector<int> ans = label(n,k,a,b);
for (int i : ans)
{
cout<<i<<" "<<i/1000<<" "<<i%1000<<"\n";
}
cout<<"\n";
cin>>q;
while (q--)
{
cin>>x>>y;
v.clear();
for (int i=0;i<n-1;++i)
{
if (x==a[i])
v.push_back(ans[b[i]]);
if (x==b[i])
v.push_back(ans[a[i]]);
}
//x = find_next_station(ans[x], ans[y], v);
cout<<find_next_station(ans[x], ans[y], v)<<"\n";
}
}**/
