#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
vector<int>paint(int n, vector<pair<int, int>>edge, int t){
int m = edge.size();
vector<int>u(m), v(m), level(m);
vector<vector<int>>g(n + 1);
for(int i = 0; i < m; i++){
tie(u[i], v[i]) = edge[i];
if(u[i] > v[i]){
swap(u[i], v[i]);
}
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
queue<int>q;
q.push(t);
vector<int>d(n + 1, -1);
d[t] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
for(int& v : g[u]){
if(d[v] == -1){
d[v] = d[u] + 1;
q.push(v);
}
}
}
for(int i = 0; i < m; i++){
level[i] = max(d[u[i]], d[v[i]]);
}
vector<int>p(m);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&] (int i, int j){
return level[i] != level[j] ? level[i] > level[j] : (u[i] != u[j] ? u[i] > u[j] : v[i] > v[j]);
});
vector<int>sz(n + 1, 1), color(m, 0);
for(int& i : p){
bool gou = (d[v[i]] > d[u[i]] || (d[v[i]] == d[u[i]] && sz[u[i]] > sz[v[i]]));
if(gou){
color[i] = 1;
sz[u[i]] += sz[v[i]];
sz[v[i]] = 0;
}
else{
sz[v[i]] += sz[u[i]];
sz[u[i]] = 0;
}
}
return color;
}
int travel(int n, int u, vector<pair<int, int>>g){
int best_v;
ll val = -1;
for(auto& [v, e] : g){
if(int(u > v) == e && maximize(val, ll(min(u, v)) * n + max(u, v))){
best_v = v;
}
}
return best_v;
}
