#include <iostream>
#include <vector>
#include <cassert>
#include <queue>
using namespace std;
using pii=pair<int, int>;
namespace
{
const int MN=1e4+13;
int N, T, d[MN];
vector<int> G[MN];
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 (int i=1; i<=N; i++) G[i].clear();
for (auto [U, V]:E)
{
G[U].push_back(V);
G[V].push_back(U);
}
bfs();
vector<int> ans;
for (auto [U, V]:E)
{
if (d[U]==d[V]+1) ans.push_back((U>V));
else
{
assert(d[U]+1==d[V]);
ans.push_back((U<V));
}
}
return ans;
}
int travel(int N, int U, vector<pii> G)
{
for (auto [x, y]:G)
{
if (!y && U<x) return x;
else if (y && U>x) return x;
}
assert(0);
}
