#include <bits/stdc++.h>
using namespace std;
#include "theseus.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
int getdir(int u,int v){
if(u>v){
return 0;
}
return 1;
}
vector<int> paint(int n,vector<pair<int,int>> edges,int t){
int m=edges.size();
vector<int> ans(m);
vector<vector<pair<int,int>>> graph(n+1);
for(int i=0;i<edges.size();i++){
int u=edges[i].first,v=edges[i].second;
graph[u].push_back({v,i}),graph[v].push_back({u,i});
}
queue<int> q;
int pa[n+1],prio[n+1],depth[n+1];
memset(depth,-1,sizeof(depth));
memset(prio,0,sizeof(prio));
for(int i=1;i<=n;i++){
pa[i]=1e9;
}
prio[t]=0,pa[t]=-1,depth[t]=0;
q.push(t);
vector<vector<int>> group(n);
while(!q.empty()){
int u=q.front();
q.pop();
group[depth[u]].push_back(u);
for(pair<int,int> &x:graph[u]){
int v=x.first;
if(depth[v]==-1){
depth[v]=depth[u]+1;
q.push(v);
}
}
}
for(int u=1;u<=n;u++){
for(pair<int,int> &x:graph[u]){
int v=x.first,idx=x.second;
if(depth[u]<depth[v]){
ans[idx]=getdir(v,u);
pa[v]=min(pa[v],u);
}
}
}
bool mark[n+1]={false};
for(int d=n-1;d>0;d--){
if(group[d].empty()){
continue;
}
sort(group[d].begin(),group[d].end());
// cout << "PHASE: " << d << endl;
// for(int u:group[d]){
// cout << u << ' ';
// }
// cout << endl;
int Max=0;
for(int u:group[d]){
Max=max(Max,prio[u]);
}
for(int x=0;x<=Max;x++){
assert(x<=13);
for(int u:group[d]){
mark[u]=false;
}
vector<pair<int,vector<int>>> s;
for(int u:group[d]){
if(prio[u]!=x){
continue;
}
if(mark[u]){
continue;
}
mark[u]=true;
s.push_back({u,{}});
for(pair<int,int> &x:graph[u]){
int v=x.first,idx=x.second;
if(prio[v]==prio[u]&&depth[v]==depth[u]&&!mark[v]){
mark[v]=true;
ans[idx]=getdir(v,u);
s.back().second.push_back(v);
for(pair<int,int> &x2:graph[v]){
int w=x2.first,idx2=x2.second;
if(w!=u&&prio[w]==prio[u]&&depth[w]==depth[u]&&!mark[w]){
ans[idx2]=getdir(v,w);
}
}
}
}
}
for(int bruh=0;bruh<s.size();bruh++){
int r=s[bruh].first;
bool flag=false;
for(int u:s[bruh].second){
if(r<pa[u]){
flag=true;
}
for(pair<int,int> &x:graph[u]){
int v=x.first,idx=x.second;
if(depth[v]==depth[u]&&prio[u]<prio[v]){
ans[idx]=getdir(u,v);
}
}
}
if(flag){
Max=max(Max,prio[r]);
prio[r]++;
}
else{
for(pair<int,int> &x:graph[r]){
int v=x.first,idx=x.second;
if(depth[v]==depth[r]&&prio[r]<prio[v]){
ans[idx]=getdir(r,v);
}
}
}
}
}
for(int u:group[d]){
prio[pa[u]]=max(prio[pa[u]],prio[u]);
}
}
return ans;
}
int travel(int n,int u,vector<std::pair<int,int>> edges){
int bst=1e9;
for(pair<int,int> &x:edges){
int v=x.first,e=x.second;
if((u>v&&!e)||(u<v&&e)){
bst=min(bst,v);
}
}
return bst;
}
