#include "Anthony.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const int MAXN = 20010;
vpi A[MAXN];
int spec[MAXN];
vi out;
int dst[MAXN];
queue<pi> Q;
void dfs(int x, int p, int val){
int nx = spec[x] + 1;
nx%=3;
for (auto v:A[x])if(v.f!=p){
spec[v.f] = nx;
dfs(v.f,x,1-val);
out[v.s] = spec[v.f];
}
}
vi LO;
std::vector<int> Mark(int N, int M, int _A, int _B,
std::vector<int> U, std::vector<int> V) {
//assert(M==N-1);
//assert(_B == 2*N);
//assert(_A>=4);
out.resize(M,0);
for (int i=0;i<M;++i){
int a=U[i];int b=V[i];
//cout<<a<<' '<<b<<'\n';
A[a].pb(b,i);A[b].pb(a,i);
}
dst[0]=1;
Q.push(mp(0,-1));
spec[0] = 2;
while (SZ(Q)){
int t = Q.front().f;
int p = Q.front().s;
Q.pop();
for (auto v:A[t])if(v.f!=p){
if (dst[v.f]!=0){
LO.pb(v.s);
}else{
spec[v.f] = (1+spec[t])%3;
out[v.s] = (1+spec[t])%3;
dst[v.f] = 1+dst[t];
Q.push(mp(v.f,t));
}
}
}
sort(ALL(LO));
LO.resize(unique(ALL(LO)) - LO.begin());
//cout<<SZ(LO)<<'\n';
for (auto i:LO){
int ind = i;
int a = U[ind];
int b = V[ind];
//cout<<"A entry "<<spec[a]<<' '<<" B entry "<<spec[b]<<' ';
if (dst[a] == dst[b]){
out[ind] = (1+spec[a])%3;
}else{
assert(abs(dst[a] - dst[b]) == 1);
if (dst[a] > dst[b])swap(a,b);
out[ind] = (1+spec[a])%3;
}
//cout<<" out "<<out[ind]<<'\n';
}
//for (auto i : out)cout<<i<<' ';cout<<'\n';
return out;
}
#include "Catherine.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
void Init(int A, int B) {
}
stack<int> p;
int fst3 = 1;
int movenum = 0;
deque<int> f6;
int brow[] = {1,0,1,1,0,0};
bool is_wrong(){
for (int i=0;i<6;++i)if (brow[i] != f6[i])return 0;
return 1;
}
int Move(std::vector<int> y) {
int a = y[0];
int b = y[1];
int c = y[2];
if (a>0&&b>0&&c>0){
assert(0);
return -1;
}
if (a==0&&b==0)return 2;
if (b==0&&c==0)return 0;
if (a==0&&c==0)return 1;
if (a==0)return 1;
if (b==0)return 2;
if (c==0)return 0;
}
