#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
#define inf 1000000000
#define mod 1000000007
std::vector<int> paint(int n, vector<pair<int,int>> edges, int t) {
vvi edg(n);
for(int i = 0; i < edges.size(); i++){
edges[i].first--;
edges[i].second--;
ll u = edges[i].first;
ll v = edges[i].second;
edg[u].push_back(v);
edg[v].push_back(u);
}
t--;
deque<ll> q = {t};
vi dist(n, inf);
dist[t] = 0;
while(!q.empty()){
ll u = q.front();
for(ll v : edg[u]){
if(dist[v] == inf){
dist[v] = dist[u] + 1;
q.push_back(v);
}
}
}
vector<int> ans(n, 0);
for(int i = 0; i < edges.size(); i++){
ll u = edges[i].first;
ll v = edges[i].second;
bool a = (u < v);
bool b = (dist[u] < dist[v]);
ans[i] = a ^ b;
}
return ans;
}
int travel(int n, int u, vector<pair<int,int>> nei) {
for(int i = 0; i < nei.size(); i++){
ll v = nei[i].first;
ll xr = nei[i].second;
ll near = xr ^ (u < v);
if(!near){
return v;
}
}
return nei[0].first;
}
