#include <iostream>
#include <vector>
#include <cassert>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
using pii=pair<int, int>;
using ti3=tuple<int, int, int>;
namespace
{
const int MN=1e4+13;
int N, T, d[MN], sz[MN];
vector<int> G[MN];
map<pii, bool> mp;
vector<ti3> edges;
void bfs()
{
for (int i=1; i<=N; i++) d[i]=-1;
queue<int> q;
d[T]=0;
q.push(T);
while (q.size())
{
int u=q.front(); q.pop();
for (int v:G[u]) if (d[v]==-1)
{
d[v]=d[u]+1;
q.push(v);
}
}
}
}
vector<int> paint(int n, vector<pii> E, int t)
{
N=n; T=t;
for (auto [U, V]:E)
{
G[U].push_back(V);
G[V].push_back(U);
}
bfs();
for (int i=1; i<=N; i++) sz[i]=1;
for (auto [U, V]:E) edges.push_back({max(d[U], d[V]), min(U, V), max(U, V)});
sort(edges.begin(), edges.end(), greater<ti3>());
for (auto [t, u, v]:edges)
{
if (d[u]==d[v]+1 || (d[u]==d[v] && sz[u]<=sz[v]))
{
mp[{u, v}]=0;
sz[v]+=sz[u];
sz[u]=0;
}
else
{
mp[{u, v}]=1;
sz[u]+=sz[v];
sz[v]=0;
}
}
vector<int> ans;
for (auto [U, V]:E) ans.push_back(mp[{min(U, V), max(U, V)}]);
return ans;
}
int travel(int N, int U, vector<pii> G)
{
int ans=0;
for (auto [x, y]:G)
{
if (!y && U<x) ans=max(ans, x);
else if (y && U>x) ans=max(ans, x);
}
assert(ans);
return ans;
}
