#include "Anthony.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
vector<int> seq = {1,0,1,1,0,0};
set<int> pos_segs = {13,6,19,9,20,26};
vector<pii> graph[20'001];
vi ans;
bool is_tree;
vi moves;
int cur_seg = 0;
bool odw[20'001];
int dist[20'001];
void dfs_color(int v, int pop, int path_ind, int pop_color)
{
forall(it,graph[v])
{
if(it.ff == pop) continue;
if(path_ind != -1)
{
ans[it.ss] = seq[path_ind];
}
else
{
ans[it.ss] = pop_color^1;
}
if(siz(graph[it.ff]) <= 2)
{
if(path_ind != -1)
{
dfs_color(it.ff,v,(path_ind+1) % siz(seq),ans[it.ss]);
}
else
{
if(pop_color == 0)
{
dfs_color(it.ff,v,1,ans[it.ss]);
}
else
{
dfs_color(it.ff,v,2,ans[it.ss]);
}
}
}
else
{
dfs_color(it.ff,v,-1,ans[it.ss]);
}
}
}
vector<int> Mark(int n, int m, int A, int B, vector<int> _U, vector<int> _V)
{
ans.resize(m);
rep(i,m)
{
graph[_U[i]].pb({_V[i],i});
graph[_V[i]].pb({_U[i],i});
}
if(B != 0)
{
if(siz(graph[0]) > 1)
{
dfs_color(0,0,-1,0);
}
else
{
dfs_color(0,0,0,0);
}
}
else
{
queue<pii> q;
q.push({0,0});
while(!q.empty())
{
pii t = q.front();
q.pop();
if(odw[t.ff]) continue;
dist[t.ff] = t.ss;
odw[t.ff] = 1;
forall(it,graph[t.ff])
{
q.push({it.ff,t.ss+1});
}
}
//rep(i,n) cout << dist[i] << " " << i << " dist\n";
rep(i,m)
{
if(dist[_U[i]] < dist[_V[i]]) swap(_U[i],_V[i]);
ans[i] = dist[_V[i]] % 3;
}
}
//rep(i,m)
//{
// cout << _U[i] << " " << _V[i] << " " << ans[i] << " tree\n";
//}
return ans;
}
void Init(int A, int B)
{
if(B != 0) is_tree =1;
else is_tree = 0;
}
int Move(vector<int> y)
{
//cout << "ruch\n";
//cout << y[0] << " " << y[1] << " y\n";
if(is_tree)
{
if(siz(moves) == 0)
{
int s = y[0] + y[1];
if(s > 2)
{
cur_seg = -1;
if(y[0] == 1)
{
moves.pb(0);
return 0;
}
else
{
moves.pb(1);
return 1;
}
}
else if(s == 1)
{
cur_seg = -1;
if(y[0] == 1)
{
moves.pb(0);
return 0;
}
else
{
moves.pb(1);
return 1;
}
}
else
{
if(y[0] >= 1)
{
y[0]--;
}
else
{
cur_seg += (1 << 0);
}
if(y[0] != 0)
{
moves.pb(0);
return 0;
}
else
{
cur_seg += (1 << 1);
moves.pb(1);
return 1;
}
}
}
else
{
//cout << cur_seg << " cur_seg\n";
if(cur_seg == -1)
{
int s = y[0]+y[1];
if(s == 1)
{
if(y[0] == 1)
{
moves.pb(0);
return 0;
}
else
{
moves.pb(1);
return 1;
}
}
int m = moves.back()^1;
moves.pb(m);
return m;
}
else
{
int s = y[0] + y[1];
if(s == 1)
{
if(y[1] == 1)
{
cur_seg += (1 << (siz(moves)+1));
}
if(siz(moves) == 3)
{
// cout << cur_seg << " move3_seg\n";
if(pos_segs.find(cur_seg) == pos_segs.end())
{
cur_seg = -1;
if(y[0] == 1)
{
moves.pb(0);
return 0;
}
else
{
moves.pb(1);
return 1;
}
}
else
{
cur_seg = -1;
return -1;
}
}
if(y[1] == 1)
{
moves.pb(1);
return 1;
}
else
{
moves.pb(0);
return 0;
}
}
else
{
int m = moves.back();
cur_seg = -1;
if(y[m^1] == 1)
{
moves.pb(m^1);
return m^1;
}
else
{
return -1;
}
}
}
}
}
else
{
set<int> pom;
rep(i,3) if(y[i] != 0) pom.insert(i);
if(siz(pom) == 1) return *pom.begin();
if(y[0] == 0) return 1;
if(y[1] == 0) return 2;
if(y[2] == 0) return 0;
}
}
#include "Catherine.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
vector<int> seq = {1,0,1,1,0,0};
set<int> pos_segs = {13,6,19,9,20,26};
vector<pii> graph[20'001];
vi ans;
bool is_tree;
vi moves;
int cur_seg = 0;
bool odw[20'001];
int dist[20'001];
void dfs_color(int v, int pop, int path_ind, int pop_color)
{
forall(it,graph[v])
{
if(it.ff == pop) continue;
if(path_ind != -1)
{
ans[it.ss] = seq[path_ind];
}
else
{
ans[it.ss] = pop_color^1;
}
if(siz(graph[it.ff]) <= 2)
{
if(path_ind != -1)
{
dfs_color(it.ff,v,(path_ind+1) % siz(seq),ans[it.ss]);
}
else
{
if(pop_color == 0)
{
dfs_color(it.ff,v,1,ans[it.ss]);
}
else
{
dfs_color(it.ff,v,2,ans[it.ss]);
}
}
}
else
{
dfs_color(it.ff,v,-1,ans[it.ss]);
}
}
}
vector<int> Mark(int n, int m, int A, int B, vector<int> _U, vector<int> _V)
{
ans.resize(m);
rep(i,m)
{
graph[_U[i]].pb({_V[i],i});
graph[_V[i]].pb({_U[i],i});
}
if(B != 0)
{
if(siz(graph[0]) > 1)
{
dfs_color(0,0,-1,0);
}
else
{
dfs_color(0,0,0,0);
}
}
else
{
queue<pii> q;
q.push({0,0});
while(!q.empty())
{
pii t = q.front();
q.pop();
if(odw[t.ff]) continue;
dist[t.ff] = t.ss;
odw[t.ff] = 1;
forall(it,graph[t.ff])
{
q.push({it.ff,t.ss+1});
}
}
//rep(i,n) cout << dist[i] << " " << i << " dist\n";
rep(i,m)
{
if(dist[_U[i]] < dist[_V[i]]) swap(_U[i],_V[i]);
ans[i] = dist[_V[i]] % 3;
}
}
//rep(i,m)
//{
// cout << _U[i] << " " << _V[i] << " " << ans[i] << " tree\n";
//}
return ans;
}
void Init(int A, int B)
{
if(B != 0) is_tree =1;
else is_tree = 0;
}
int Move(vector<int> y)
{
//cout << "ruch\n";
//cout << y[0] << " " << y[1] << " y\n";
if(is_tree)
{
if(siz(moves) == 0)
{
int s = y[0] + y[1];
if(s > 2)
{
cur_seg = -1;
if(y[0] == 1)
{
moves.pb(0);
return 0;
}
else
{
moves.pb(1);
return 1;
}
}
else if(s == 1)
{
cur_seg = -1;
if(y[0] == 1)
{
moves.pb(0);
return 0;
}
else
{
moves.pb(1);
return 1;
}
}
else
{
if(y[0] >= 1)
{
y[0]--;
}
else
{
cur_seg += (1 << 0);
}
if(y[0] != 0)
{
moves.pb(0);
return 0;
}
else
{
cur_seg += (1 << 1);
moves.pb(1);
return 1;
}
}
}
else
{
//cout << cur_seg << " cur_seg\n";
if(cur_seg == -1)
{
int s = y[0]+y[1];
if(s == 1)
{
if(y[0] == 1)
{
moves.pb(0);
return 0;
}
else
{
moves.pb(1);
return 1;
}
}
int m = moves.back()^1;
moves.pb(m);
return m;
}
else
{
int s = y[0] + y[1];
if(s == 1)
{
if(y[1] == 1)
{
cur_seg += (1 << (siz(moves)+1));
}
if(siz(moves) == 3)
{
// cout << cur_seg << " move3_seg\n";
if(pos_segs.find(cur_seg) == pos_segs.end())
{
cur_seg = -1;
if(y[0] == 1)
{
moves.pb(0);
return 0;
}
else
{
moves.pb(1);
return 1;
}
}
else
{
cur_seg = -1;
return -1;
}
}
if(y[1] == 1)
{
moves.pb(1);
return 1;
}
else
{
moves.pb(0);
return 0;
}
}
else
{
int m = moves.back();
cur_seg = -1;
if(y[m^1] == 1)
{
moves.pb(m^1);
return m^1;
}
else
{
return -1;
}
}
}
}
}
else
{
set<int> pom;
rep(i,3) if(y[i] != 0) pom.insert(i);
if(siz(pom) == 1) return *pom.begin();
if(y[0] == 0) return 1;
if(y[1] == 0) return 2;
if(y[2] == 0) return 0;
}
}
