#include "conveyor.h"
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
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];
int found[N];
vector<int> active;
map<pair<int, int>, int> idx;
vector<int> lastquery, putball, nextdir, dir;

void setansdir(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;
  if (dir[id] == -1){
    dir[id] = needdir;
  }
}

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 setnextdir(int u, int v, int val){
  if (idx.count(pair{u, v})) nextdir[idx[{u, v}]] = val;
  if (idx.count(pair{v, u})) nextdir[idx[{v, u}]] = val;
}

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

void process2(vector<int> path){
  if (sz(path) == 3){
    if (lastquery[path[1]]){
      setansdir(path[0], path[1]);
      setansdir(path[2], path[1]);
      found[path[1]] = 1;
    }
    putball[path[1]] = 1;
    setnextdir(path[0], path[1], 0);
    setnextdir(path[1], path[2], 1);
    return;
  }
  int start = (sz(path) % 3 == 2? 2 : 1);
  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 ((i > 1 && lastquery[path[i - 1]]) || (i == 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){
  if (sz(path) == 3){
    if (lastquery[path[1]]){
      setansdir(path[0], path[1]);
      setansdir(path[1], path[2]);
      found[path[1]] = 1;
    }
    putball[path[1]] = 1;
    setnextdir(path[0], path[1], 1);
    setnextdir(path[1], path[2], 0);
    return;
  }
  int start = (sz(path) % 3 == 2? 2 : 1);
  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 ((i > 1 && lastquery[path[i - 1]]) || (i == 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){
  if (sz(path) == 3){
    if (lastquery[path[1]]){
      setansdir(path[1], path[0]);
      setansdir(path[2], path[1]);
    }
    else if (!found[path[1]]){
      setansdir(path[1], path[0]);
      setansdir(path[1], path[2]);
    }
  }
  else{
    int start = (sz(path) % 3 == 2? 2 : 1);
    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 (int i = 1; i < sz(path) - 1; i++) active[path[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 (!active[v]){
    goto end;
  }
  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();
  }
  end: for (auto u : g[v]){
    if (active[u]) dfs2(u, v);
  }
  for (auto u : g[v]){
    if (!active[u]) 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, -1);
  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);
    paths.clear();
  }
  Answer(dir);
}