#include <bits/stdc++.h>
#include "Anthony.h"
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
namespace {
const int N = 2e4 + 10;
int col[N];
vector<pii> G[N];
int pat[] = {0, 1, 0, 0, 1, 1};
void DFS(int u, int p, int pt = 0){
int cnt = 0;
for(auto [adj, id] : G[u]){
if(adj != p) cnt ++;
}
if(cnt == 0) return ;
if(cnt == 1){
pt = (pt + 1) % 6;
} else {
pt = (pat[pt] == 0 ? 1 : 0);
}
if(u == 0) pt = 0;
for(auto [adj, id] : G[u]){
if(adj != p){
DFS(adj, u, pt);
col[id] = pat[pt];
}
}
}
}
vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
assert(m == n - 1);
assert(B >= 6);
//cerr << "Salam\n";
for(int i = 0; i < m; i++){
G[U[i]].pb({V[i], i});
G[V[i]].pb({U[i], i});
}
DFS(0, -1);
//cerr << "Bye\n";
vector<int> C(m, 0);
for(int i = 0; i < m; i++) C[i] = col[i];
return C;
}
#ifdef safar
int main(){
int n;
cin >> n;
vector<int> U1, V1, R;
int u, v;
for(int i = 0; i < n - 1; i++){
cin >> u >> v;
U1.pb(u);
V1.pb(v);
}
R = Mark(n, n - 1, 2, 6, U1, V1);
for(auto x : R) cerr << x << '\n';
}
#endif
/*
10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
7 9
9 10
*/
#include <bits/stdc++.h>
#include "Catherine.h"
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
namespace {
vector<int> vis, pa;
bool UP = false;
int MoveUp(vector<int> y){
int deg = (vis.size() > 0 ? 1 : 0);
for(auto x : y) deg += x;
//cerr << "% " << deg << '\n';
if(deg == 1 and !vis.empty()){
return -1;
}
if(deg <= 2){
for(int i = 0; i < 2; i++)
if(y[i])
return i;
}
//cerr << "$$ " << y[0] << ' ' << y[1] << '\n';
int mn = 1'000'000'000;
for(auto x : y) mn = min(x, mn);
if(mn == 0) return -1;
if(vis.empty())
return (y[0] == 1 ? 0 : 1);
return 1 - vis.back();
}
int Hand(int x){
//cerr << "# " << x << '\n';
if(x == -1) vis.pb(vis.back());
else vis.pb(x);
pa.pb(vis.back());
return x;
}
bool Rev(){
int sm = 3;
for(auto x : pa) sm -= x;
pa.pb(sm);
for(int i = 0; i < 6; i++) pa.pb(pa[i]);
for(int i = 0; i + 4 < (int)pa.size(); i ++){
if((pa[i] == 0) && (pa[i+1] == 0) && (pa[i + 2] == 1) && (pa[i + 3] == 1)){
return true;
}
}
return false;
}
} // namespace
void Init(int A, int B){
assert(A == 2);
assert(B >= 6);
}
int Move(vector<int> y){
//cerr << "O\n";
int deg = (vis.size() > 0 ? 1 : 0);
for(auto x : y) deg += x;
if(deg >= 3) UP = true;
if(deg == 1) UP = true;
//cerr << "A\n";
if(UP) return Hand(MoveUp(y));
//cerr << "E\n";
if(vis.empty()){
int idx;
for(int i = 0; i < 2; i++) if(y[i]) idx = i;
y[idx] -= 1;
int idx2;
for(int i = 0; i < 2; i++) if(y[i]) idx2 = i;
pa.pb(idx2);
return Hand(idx);
}
if(pa.size() < 4){
int idx;
for(int i = 0; i < 2; i++) if(y[i]) idx = i;
return Hand(idx);
}
int idx;
for(int i = 0; i < 2; i++) if(y[i]) idx = i;
pa.pb(idx);
if(Rev()){
UP = true;
return Hand(-1);
}
UP = true;
return Hand(MoveUp(y));
}
