#include <iostream>
#include <vector>
#include <cassert>
#include <queue>
using namespace std;
using pii=pair<int, int>;
namespace
{
const int MN=1e4+13;
int N, dep[MN]; bool col[MN];
vector<int> G[MN];
void dfs(int u, int p)
{
if (!p)
{
for (int v:G[u])
{
col[v]=0;
dfs(v, u);
}
return;
}
int cnt=G[u].size()-1;
if (!cnt) return;
else if (cnt==1)
{
for (int v:G[u]) if (v!=p)
{
if (p<v) col[v]=col[u];
else col[v]=!col[u];
dfs(v, u);
}
}
else
{
for (int v:G[u]) if (v!=p)
{
col[v]=!col[u];
dfs(v, u);
}
}
}
}
vector<int> paint(int n, vector<pii> E, int T)
{
N=n;
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);
}
dep[T]=0; dfs(T, 0);
vector<int> ans;
for (auto [U, V]:E)
{
if (dep[U]>dep[V]) ans.push_back(col[U]);
else ans.push_back(col[V]);
//cerr<<ans.back()<<' ';
} //cerr<<endl;
return ans;
}
int travel(int N, int U, vector<pii> G)
{
if (G.size()!=2)
{
int c1=0, c0=0;
for (auto [x, y]:G)
{
if (y) c1++;
else c0++;
}
assert(c1==1 || c0==1);
if (c1==1) { for (auto [x, y]:G) if (y) return x; }
else { for (auto [x, y]:G) if (!y) return x; }
assert(0);
}
if (G[0].second^G[1].second) return max(G[0].first, G[1].first);
else return min(G[0].first, G[1].first);
}
