#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> Mark2(int n, int m, int A, int B, vector<int> U, vector<int> V) {
//cerr << "Salam\n";
for(int i = 0; i < m; i++){
G[U[i]].pb({V[i], i});
G[V[i]].pb({U[i], i});
}
queue<int> Q;
vector<int> dep(n, 1'000'000'000);
dep[0] = 0;
Q.push(0);
int fr;
while(!Q.empty()){
fr = Q.front();
Q.pop();
for(auto [adj, id] : G[fr]){
if(dep[adj] > dep[fr] + 1){
dep[adj] = dep[fr] + 1;
Q.push(adj);
}
}
}
//cerr << "Bye\n";
vector<int> C(m, 0);
for(int i = 0; i < m; i++) C[i] = min(dep[U[i]], dep[V[i]]) % 3;
return C;
}
vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
if(B == 0){
return Mark2(n, m, A, B, U, 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
/*
20 30 3 0 4
1 9
0 11
7 9
2 8
6 13
3 4
6 16
8 14
6 17
10 12
9 13
3 10
13 17
7 12
11 15
9 17
18 19
3 18
10 19
4 18
4 19
2 4
10 18
1 12
3 12
2 3
4 14
2 14
13 15
5 14
*/
#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;
}
int state = 0;
int Move2(vector<int> y){
if(!vis.empty()) y[vis.back()] ++;
if(y[0] + y[1] == 0) return 2;
if(y[0] + y[2] == 0) return 1;
if(y[1] + y[2] == 0) return 0;
if(y[2] == 0) return 0;
if(y[0] == 0) return 1;
if(y[1] == 0) return 2;
return -1;
}
} // namespace
void Init(int A, int B){
if(B == 0) state = 1;
}
int Move(vector<int> y){
if(state == 1) return Hand(Move2(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));
}
