#include "stations.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef ll itn;
#define ff first
#define ss second
ll n;
ll cnt[1007];
vector<int>g[1007];
int get_level(int v) {
//v++;
return log2(v);
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> lbl(n);
for (int i = 0; i < n; i++) {
lbl[i] = i + 1;
}
return lbl;
}
bool papa(int s, int t) {
//cout << "IsPapa: " << s << " " << t << endl;
if (s == t)return true;
int ls = get_level(s);
int lt = get_level(t);
if (ls >= lt)return false;
int lvl = lt - ls;
int vl = (1 << lvl);
int sk = vl * s;
int vj = sk + vl - 1;
//cout << ls << " " << lt << " " << lvl << " " << vl << " " << sk << " " << vj << endl;
return (t >= sk && t <= vj);
}
int find_next_station(int s, int t, vector<int> c) {
//cout << "Doing: " << s << " " << t << endl;
if (c.size() == 1)return c[0];
if (papa(s, t)) {
if (papa(2 * s, t))return 2 * s;
else return 2 * s + 1;
}
else return s / 2;
}
/*
1
8 1000
0 1
0 2
1 3
1 4
3 5
3 6
5 7
5
7 2 5
2 3 0
6 5 3
7 4 5
6 4 3
1 8 1000 0 1 0 2 1 3 1 4 3 5 3 6 5 7 5 7 2 5 2 3 0 6 5 3 7 4 5 6 4 3
1 8 1000
0 1
0 2
1 3
1 4
2 5
2 6
3 7
5
7 2 3
1 7 3
2 5 5
0 5 2
5 0 2
*/
