#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define double long double
#define gcd __gcd
#define lcm(a, b) ((a)/gcd(a, b)*(b))
#define sqrt sqrtl
#define log2 log2l
#define log10 log10l
#define floor floorl
#define to_string str
#define yes cout << "YES"
#define no cout << "NO"
#define trav(i, a) for (auto &i: (a))
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)a.size()
#define Max(a) *max_element(all(a))
#define Min(a) *min_element(all(a))
#define Find(a, n) (find(all(a), n) - a.begin())
#define Count(a, n) count(all(a), n)
#define Upper(a, n) (upper_bound(all(a), n) - a.begin())
#define Lower(a, n) (lower_bound(all(a), n) - a.begin())
#define next_perm(a) next_permutation(all(a))
#define prev_perm(a) prev_permutation(all(a))
#define sorted(a) is_sorted(all(a))
#define sum(a) accumulate(all(a), 0)
#define sumll(a) accumulate(all(a), 0ll)
#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))
#define Unique(a) Sort(a), (a).resize(unique(all(a)) - a.begin())
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define clz __builtin_clz
#define clzll __buitlin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define open(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define fileopen(s) open((string(s) + ".inp").c_str()), write((string(s) + ".out").c_str());
#define For(i, a, b) for (auto i = (a); i < (b); ++i)
#define Fore(i, a, b) for (auto i = (a); i >= (b); --i)
#define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
#define ret(s) return void(cout << s);
#include "Anthony.h"
vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
if (A >= 3) {
vector<vector<int>> g(n);
For(i,0,m) g[U[i]].pb(V[i]), g[V[i]].pb(U[i]);
vector<int> d(n, -1);
queue<int> q; q.push(0); d[0] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
trav(v,g[u]){
if (d[v] == -1) d[v] = d[u] + 1, q.push(v);
}
}
vector<int> w(m);
For(i,0,m) w[i] = min(d[U[i]], d[V[i]]) % 3;
return w;
}
vector<int> w(m), d{0, 1, 0, 0, 1, 1};
vector<vector<pair<int, int>>> g(n);
For(i,0,m) g[U[i]].eb(V[i], i), g[V[i]].eb(U[i], i);
auto dfs = [&](auto &&dfs, int u, int p, int l)->void{
for (auto [v, i]: g[u]) if (v != p) {
if (sz(g[u]) != 2) w[i] = d[l]^1, dfs(dfs, v, u, w[i]);
else w[i] = d[(l + 1) % 6], dfs(dfs, v, u, (l + 1) % 6);
}
};
dfs(dfs, 0, -1, 5);
return w;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define double long double
#define gcd __gcd
#define lcm(a, b) ((a)/gcd(a, b)*(b))
#define sqrt sqrtl
#define log2 log2l
#define log10 log10l
#define floor floorl
#define to_string str
#define yes cout << "YES"
#define no cout << "NO"
#define trav(i, a) for (auto &i: (a))
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)a.size()
#define Max(a) *max_element(all(a))
#define Min(a) *min_element(all(a))
#define Find(a, n) (find(all(a), n) - a.begin())
#define Count(a, n) count(all(a), n)
#define Upper(a, n) (upper_bound(all(a), n) - a.begin())
#define Lower(a, n) (lower_bound(all(a), n) - a.begin())
#define next_perm(a) next_permutation(all(a))
#define prev_perm(a) prev_permutation(all(a))
#define sorted(a) is_sorted(all(a))
#define sum(a) accumulate(all(a), 0)
#define sumll(a) accumulate(all(a), 0ll)
#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))
#define Unique(a) Sort(a), (a).resize(unique(all(a)) - a.begin())
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define clz __builtin_clz
#define clzll __buitlin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define open(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define fileopen(s) open((string(s) + ".inp").c_str()), write((string(s) + ".out").c_str());
#define For(i, a, b) for (auto i = (a); i < (b); ++i)
#define Fore(i, a, b) for (auto i = (a); i >= (b); --i)
#define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
#define ret(s) return void(cout << s);
#include "Catherine.h"
int A, B, lst;
bool c;
vector<int> t, d{0, 1, 0, 0, 1, 1};
void Init(int _A, int _B) {
A = _A, B = _B;
lst = -1;
c = 0;
t.clear();
}
int Move(vector<int> w) {
if (A >= 3) {
vector<int> a;
For(i,0,3) if (w[i]) a.pb(i);
if (sz(a) == 2 && a[0] == 0 && a[1] == 2) return 2;
return a[0];
}
int g = (lst != -1) + w[0] + w[1];
if (g != 2) {
if (~lst) ++w[lst];
c = 1;
int i = (w[0] < w[1]);
if (i == lst) return -1;
return lst = i;
}
if (c) return lst = (w[0] < w[1]);
For(i,0,w[0]) t.pb(0);
For(i,0,w[1]) t.pb(1);
if (sz(t) == 5) {
bool s = 0;
For(i,0,6){
bool o = 1;
For(j,0,5) o&=t[j] == d[(i + j) % 6];
s|=o;
}
c = 1;
if (s) {
t.clear();
return -1;
}
lst = t.back(); t.clear();
return lst;
}
return lst = t.back();
}
