#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=2e4+9;
vector<int>a[maxn];
vector<pii>g[maxn];
bool vis[maxn];
int d[maxn];
int b[6]={0,1,0,0,1,1};
vector<int>id;
int msk[maxn];
int xr=1;
void dfs(int u,int par){
int cnt=0;
for (auto v:g[u]){
if (v.fi==par)continue;
cnt++;
}
if (cnt>1||cnt==0){
int lst=0;
for1(i,0,sz(id)-1){
msk[id[i]]=(b[i%6]^xr);
lst=msk[id[i]];
}
id.clear();
xr=(lst^1);
}
int xd=xr;
for (auto v:g[u]){
if (v.fi==par)continue;
id.pb(v.se);
dfs(v.fi,u);
xr=xd;
}
}
std::vector<int> Mark(int N, int M, int A, int B,std::vector<int> U, std::vector<int> V) {
int n=N,m=M;
if (B==0){
std::vector<int> x(M);
for1(i,0,m-1){
a[U[i]].pb(V[i]);
a[V[i]].pb(U[i]);
}
vis[0]=1;
queue<int>t;
t.push(0);
while (!t.empty()){
auto u=t.front();
t.pop();
for (auto v:a[u]){
if (vis[v])continue;
d[v]=d[u]+1;
t.push(v);
vis[v]=1;
}
}
for (int i = 0; i < M; ++i) {
int u=U[i],v=V[i];
if (d[u]==d[v]){
int t1=(d[u]%3),t2=(t1+1)%3;
if (t1==1||t2==1)x[i]|=(1<<0);
if (t1==2||t2==2)x[i]|=(1<<1);
x[i]--;
continue;
}
if (d[u]>d[v])swap(u,v);
int mask=0;
if (d[u]%3==2||d[v]%3==2)mask|=(1<<1);
if (d[u]%3==1||d[v]%3==1)mask|=(1<<0);
x[i]=mask-1;
}
return x;
}
else {
for1(i,0,m-1){
g[U[i]].pb({V[i],i});
g[V[i]].pb({U[i],i});
}
dfs(0,0);
vector<int>x(M);
for1(i,0,m-1)x[i]=msk[i];
return x;
}
}
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
namespace {
int A, B;
int step = 0;
} // namespace
int c[12]={0,1,0,0,1,1,0,1,0,0,1,1};
set<int>patt;
void Init(int A, int B) {
::A = A;
::B = B;
if (B==0){
return;
}
for1(i,0,11-4+1){
int cc=0,sum=0;
for1(j,i,i+3){
sum+=c[j]*(1<<cc);
cc++;
}
patt.insert(sum);
}
}
int cnt[3];
bool detact=false;
int lst=-1;
vector<int>xx;
int Move(std::vector<int> y) {
//
if (B==0){
int ct=0;
for1(i,0,2){
if (y[i]!=0)ct++;
}
if (ct==1){
for1(i,0,2){
if (y[i]!=0)return i;
}
}
for1(i,0,2)cnt[i]=0;
for1(i,0,2){
if (y[i]!=0){
int j=i+1;
for1(k,0,1){
if (j>>k&1){
cnt[(1<<k)]++;
}
else {
cnt[0]++;
}
}
}
}
for1(i,0,2){
if (cnt[i]==2){
int ans=i;
int gg=(i-1+3)%3;
ans+=gg;
return ans-1;
}
}
}
//
if (!detact){
step++;
int deg=0;
for1(i,0,A-1){
deg+=y[i];
}
if (deg==1){
for1(i,0,A-1){
if (y[i]!=0){
xx.pb(i);
lst=i;
return i;
}
}
}
else if (deg==0){
step--;
lst=xx.back();
xx.pop_back();
detact=1;
return -1;
}
deg+=(step>1);
if (deg==2){
for1(i,0,A-1){
if (y[i]!=0){
xx.pb(i);
lst=i;
return i;
}
}
}
if (deg>2){
if (lst!=-1)y[lst]++;
if (y[lst]==1){
lst=xx.back();
xx.pop_back();
detact=1;
step--;
return -1;
}
step=0;
detact=1;
for1(i,0,A-1){
if (y[i]==1){
lst=i;
return i;
}
}
}
}
else {
if (step){
lst=xx.back();
xx.pop_back();
step--;
return -1;
}
else {
int deg=0;
for1(i,0,A-1){
deg+=y[i];
}
if (deg==1){
for1(i,0,A-1)if (y[i]!=0)return i;
}
else {
if (lst!=-1)y[lst]++;
for1(i,0,A-1)if (y[i]==1)return i;
}
}
}
}
