#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e4 + 1;
//#include "stations.h"
bool wt[maxn];
vt<int> g[maxn];
vt<pii> asgn;
int in[maxn], out[maxn], cnt;
void dfs(int i, int p){
in[i] = cnt++;
for(auto j : g[i]){
if(j == p)continue;
wt[j] = wt[i] ^ 1;
dfs(j, i);
}
out[i] = cnt++;
if(wt[i])asgn.pb({out[i], i});
else asgn.pb({in[i], i});
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
cnt = 0;
asgn.clear();
for(int i = 0; i <= n; i++)g[i].clear();
for(int i = 0; i < n - 1; i++){
g[u[i]].pb(v[i]), g[v[i]].pb(u[i]);
}
wt[0] = 0;
dfs(0, -1);
cnt = 0;
sort(all(asgn));
for(auto i : asgn){
labels[i.ss] = cnt++;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
sort(all(c));
if(s < c[0]){
for(auto i : c){
if(s <= t && t <= i)return i;
}
return c.back();
}
else {
reverse(all(c));
for(auto i : c){
if(s >= t && t >= i)return i;
}
return c.back();
}
}
//void solve() {
//}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//int times = 1;
////cin >> times;
//for(int i = 1; i <= times; i++) {
//solve();
//}
//return 0;
//}
//#include "stations.h"
//#include <cstdio>
//#include <cassert>
//#include <map>
//#include <vector>
//#include <algorithm>
//static int max_label = 0;
//static int r, n, k, q;
//static std::vector<int> u, v, labels, answers;
//static std::map<int, int> reverse_labels;
//static std::vector<std::vector<int>> adjlist;
//static int s, t, w;
//static std::vector<int> c;
//int main() {
//assert(scanf("%d", &r) == 1);
//for (int tc = 0; tc < r; tc++) {
//assert(scanf("%d%d", &n, &k) == 2);
//u.resize(n - 1);
//v.resize(n - 1);
//adjlist.clear();
//adjlist.resize(n);
//for (int i = 0; i < n - 1; i++) {
//assert(scanf("%d%d", &u[i], &v[i]) == 2);
//adjlist[u[i]].push_back(v[i]);
//adjlist[v[i]].push_back(u[i]);
//}
//labels = label(n, k, u, v);
//if ((int)labels.size() != n) {
//printf("Number of labels not equal to %d\n", n);
//exit(0);
//}
//reverse_labels.clear();
//for (int i = 0; i < n; i++) {
//if (labels[i] < 0 || labels[i] > k) {
//printf("Label not in range 0 to %d\n", k);
//exit(0);
//}
//if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
//printf("Labels not unique\n");
//exit(0);
//}
//reverse_labels[labels[i]] = i;
//if (labels[i] > max_label) {
//max_label = labels[i];
//}
//}
//assert(scanf("%d", &q) == 1);
//for (int i = 0; i < q; i++) {
//assert(scanf("%d%d%d", &s, &t, &w) == 3);
//c.clear();
//for (int v : adjlist[s]) {
//c.push_back(labels[v]);
//}
//std::sort(c.begin(), c.end());
//int answer = find_next_station(labels[s], labels[t], c);
//if (!std::binary_search(c.begin(), c.end(), answer)) {
//printf("Label %d returned by find_next_station not found in c\n", answer);
//exit(0);
//}
//answers.push_back(reverse_labels[answer]);
//}
//}
//printf("%d\n", max_label);
//for (int index : answers) {
//printf("%d\n", index);
//}
//exit(0);
//}
