#include <vector>
#include <cassert>
#include <queue>
#include <iostream>
using namespace std;
using pii=pair<int, int>;
namespace
{
const int MN=1e4+13;
int N, T;
vector<int> G[MN];
int d[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;
int mx=N/2;
for (auto [U, V]:E) ans.push_back((mx-min(d[U], d[V]))&1);
//for (int i:ans) cerr<<i<<' '; cerr<<endl;
return ans;
}
int travel(int N, int U, vector<pii> G)
{
//cerr<<U<<endl;
if (G.size()==2)
{
if (G[0].second==1)
{
assert(G[1].second==0);
return G[0].first;
}
else
{
assert(G[1].second==1);
return G[1].first;
}
}
assert(G.size()==3);
int c0=0, c1=0;
for (auto [x, y]:G)
{
if (y) c1++;
else c0++;
}
//cerr<<c0<<' '<<c1<<endl;
if (c1<c0) { for (auto [x, y]:G) if (y) return x; }
else { for (auto [x, y]:G) if (!y) return x; }
assert(0);
}
