#include "conveyor.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
// #define endl '\n'

const int N = 1e5 + 20;

vector<int> g[N];
vector<int> active;
map<pair<int, int>, int> idx;
vector<int> lastquery, putball, nextdir, dir;

void setansdir(int u, int v){
  if (idx.count(pair{u, v})) dir[idx[{u, v}]] = 0;
  if (idx.count(pair{v, u})) dir[idx[{v, u}]] = 1;
}

void setnextdir(int u, int v){
  int id, needdir;
  if (idx.count(pair{u, v})){
    id = idx[{u, v}], needdir = 0;
  }
  else if (idx.count(pair{v, u})) id = idx[{v, u}], needdir = 1;
  else return;
  nextdir[id] = needdir ^ dir[id];
}

void process1(vector<int> path){
  int start = (sz(path) % 3 == 2? 1 : 0);
  for (int i = start; i < sz(path) - 1; i += 3) putball[path[i]] = 1;
}

void process2(vector<int> path){
  int start = (sz(path) % 3 == 2? 1 : 2);
  for (int i = start; i < sz(path) - 1; i += 3){
    if (lastquery[path[i]]){
      setansdir(path[i - 1], path[i]);
      setansdir(path[i + 1], path[i]);
    }
    else if (path[i - 1] != -1 && lastquery[path[i - 1]]){
      setansdir(path[i], path[i - 1]);
      setnextdir(path[i - 1], path[i]);
    }
    else{
      setansdir(path[i], path[i + 1]);
      setnextdir(path[i + 1], path[i]);
    }
    putball[path[i]] = 1;
  }
}

void process3(vector<int> path){
  int start = (sz(path) % 3 == 2? 1 : 2);
  for (int i = start; i < sz(path) - 1; i += 3){
    if (lastquery[path[i]]){
      setansdir(path[i - 1], path[i]);
      setansdir(path[i + 1], path[i]);
    }
    else if (path[i - 1] != -1 && lastquery[path[i - 1]]){
      setansdir(path[i], path[i - 1]);
    }
    else{
      setansdir(path[i], path[i + 1]);
    }
    setnextdir(path[i], path[i - 1]);
    setnextdir(path[i], path[i + 1]);
  }
  for (int i = (start == 1? 2 : 0); i < sz(path) - 1; i += 3){
    if (i) putball[path[i]] = 1;
    else putball[path[i + 1]] = 1;
  }
}

void process4(vector<int> path){
  int start = (sz(path) % 3 == 2? 1 : 2);
  for (int i = (start == 1? 2 : 0); i < sz(path) - 1; i += 3){
    if (lastquery[path[i]]) setansdir(path[i + 1], path[i]);
    else setansdir(path[i], path[i + 1]);
  }
  setnextdir(path[1], path[0]);
  setnextdir(path.end()[-2], path.end()[-1]);
  for (auto i : path) active[i] = 0;
}

vector<vector<int>> paths;
vector<int> curpath;

void dfs1(int v, int p){
  if (v != p) g[v].erase(find(all(g[v]), p));
  for (auto u : g[v]){
    dfs1(u, v);
  }
}

void dfs2(int v, int p){
  int c = 0;
  for (auto u : g[v]){
    c += active[u];
  }
  if (c <= 1){
    if (curpath.empty()){
      curpath.pb(p != v && active[p]? p : -1);
    }
    curpath.pb(v);
  }
  if (c == 0){
    curpath.pb(-1);
    if (sz(curpath) > 3 || curpath[0] != -1) paths.pb(curpath);
    curpath.clear();
  }
  if (!curpath.empty() && p != v && p == curpath.back()){
    curpath.pb(v);
    paths.pb(curpath);
    curpath.clear();
  }
  for (auto u : g[v]){
    dfs2(u, v);
  }
}

void Solve(int n, std::vector<int> a, std::vector<int> b){
  for (int i = 0; i < n - 1; i++){
    idx[{a[i], b[i]}] = i;
    g[a[i]].pb(b[i]);
    g[b[i]].pb(a[i]);
  }
  active = vector<int>(n, 1);
  putball = vector<int>(n, 0);
  dir = vector<int>(n - 1, 0);
  nextdir = vector<int>(n - 1, 0);
  dfs1(0, 0);
  while (1){
    dfs2(0, 0);
    if (paths.empty()) break;
    for (auto p : paths) process1(p);
    lastquery = Query(nextdir, putball);
    fill(all(putball), 0);
    for (auto p : paths) process2(p);
    lastquery = Query(nextdir, putball);
    fill(all(putball), 0);
    for (auto p : paths) process3(p);
    lastquery = Query(nextdir, putball);
    fill(all(putball), 0);
    for (auto p : paths) process4(p);
    fill(all(putball), 0);
  }
  Answer(dir);
}