#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e4;
vector<int> paint(int n, vector<pair<int,int>> e, int t){
t--;
vector<ll> g[n];
for(auto i:e){
ll u, v;
tie(u,v)=i; u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
ll dist[n]; dist[t]=0;
queue<ll> q; q.push(t);
bool vis[n]={}; vis[t]=1;
while(!q.empty()){
ll curr=q.front();
q.pop();
for(auto nxt:g[curr]){
if(!vis[nxt]){
dist[nxt]=dist[curr]+1;
vis[curr]=1;
q.push(nxt);
}
}
}
vector<int> ans;
for(auto i:e){
ll u, v;
tie(u,v)=i; u--; v--;
if(dist[v]<dist[u]){ // u -> v
if(u<v) ans.push_back(1);
else ans.push_back(0);
}
else{ // v -> u
if(u>v) ans.push_back(1);
else ans.push_back(0);
}
}
return ans;
}
int travel(int n, int u, vector<pair<int,int>> nxt) {
for(auto i:nxt){
if((i.second==1 && i.first>u) || (i.second==0 && i.first<u)) return i.first;
}
return nxt[0].first;
}
