#include "Anthony.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
const int MAXN = 200228;
vector<pair<int, int> > g[MAXN];
int dist[MAXN];
bool used[MAXN];
int c[6] = {1, 1, 0, 0, 1, 0};
vector<int> st;
int head[MAXN];
int ps[MAXN];
bool xored[MAXN];
void dfs(int u, int pr = -1) {
int cnt = 0;
int deg = sz(g[u]);
for (auto h: g[u]) {
if (h.first != pr) {
if (pr == -1) {
st[h.second] = 0;
head[h.first] = h.second;
ps[h.second] = 0;
} else {
if (deg >= 3) {
st[h.second] = st[head[u]] ^ 1;
head[h.first] = h.second;
if (st[h.second] == 1) {
ps[h.second] = 0;
} else {
ps[h.second] = 2;
}
} else {
st[h.second] = c[(ps[head[u]] + 1) % 6];
ps[h.second] = (ps[head[u]] + 1) % 6;
head[h.first] = h.second;
}
}
dfs(h.first, u);
}
}
}
vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
for (int i = 0; i < m; i++) {
g[U[i]].pb({V[i], i});
g[V[i]].pb({U[i], i});
}
if (A == 2) {
st.resize(m);
dfs(0);
return st;
}
for (int i = 0; i < n; i++) {
dist[i] = 0;
used[i] = false;
}
vector<int> st(m, 0);
queue<int> q;
q.push(0);
dist[0] = 0;
used[0] = true;
while (!q.empty()) {
int a = q.front();
q.pop();
for (auto h: g[a]) {
if (!used[h.first]) {
st[h.second] = dist[a] % 3;
dist[h.first] = dist[a] +1;
used[h.first] = true;
q.push(h.first);
}
}
}
for (int i = 1; i < n; i++) {
int pos = (dist[i] - 1) % 3;
for (auto h: g[i]) {
if (dist[i] == dist[h.first] + 1) {
st[h.second] = pos;
} else {
st[h.second] = (pos + 1) % 3;
}
}
}
for (auto x: st) {
cout << x << endl;
}
return st;
}
#include "Catherine.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
bool kek = false;
int cs[12] = {1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0};
void Init(int A, int B) {
if (A == 2) {
kek = true;
}
//reverse(cs, cs + 12);
}
int f = 1;
int last;
vector<int> cur;
bool bad = false;
int Move(vector<int> y) {
if (kek) {
f--;
// cout << y[0] << ' ' << y[1] << endl;
if (y[0] == 0 && y[1] == 0) {
bad = false;
return -1;
}
int sum = y[0] + y[1];
if ((f == 0 && sum >= 3) || (f < 0 && sum >= 2)) {
if (y[0] == 0 || y[1] == 0) {
bad = false;
return -1;
}
bad = false;
if (f < 0) {
last ^= 1;
return last;
}
last = y[0] < y[1] ? 0: 1;
return last;
}
if (f == 0) {
bad = true;
last = y[1] ? 1: 0;
if (y[last ^ 1]) {
cur.pb(last ^ 1);
} else if (y[last] >= 2) {
cur.pb(last);
}
if (sum == 1) {
bad = false;
}
cur.pb(last);
return last;
}
if (y[0] >= 2) {
bad = false;
return -1;
}
if (y[1] >= 2) {
bad = false;
return -1;
}
if (!bad) {
last = y[1] ? 1: 0;
return last;
}
last = y[1] ? 1: 0;
cur.pb(last);
bool ok = false;
for (int i = 0; i <= 12 - sz(cur); i++) {
bool bad = false;
for (int j = 0; j < sz(cur); j++) {
if (cur[sz(cur) - j - 1] != cs[i + j]) {
bad = true;
break;
}
}
if (!bad) {
ok = true;
}
}
if (!ok) {
bad = false;
return -1;
}
return last;
}
vector<int> st;
for (int i = 0; i < sz(y); i++) {
if (y[i] != 0) {
st.pb(i);
}
}
if (sz(st) == 0) {
return -1;
}
if (sz(st) == 1) {
return st[0];
}
if ((st[0] + 1) % 3 != st[1]) {
swap(st[0], st[1]);
}
return st[0];
}
