#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using i64 = int64_t;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;
constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();
#define RANGE(x) begin(x), end(x)
template <typename... T>
void DBG(T&&... args) {
//((cerr << args << ' '), ...) << '\n';
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
out << '{';
for (size_t i = 0; i < vec.size()-1; ++i)
out << vec[i] << ", ";
out << vec.back() << '}';
return out;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
out << '(' << pr.first << ", " << pr.second << ')';
return out;
}
namespace {
vi Mark2d(int N, vi &U, vi &V) {
int M = N-1;
vi X(M, -1);
vector<vector<pair<int,int>>> adj(N);
for (int i = 0; i < M; ++i) {
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
DBG(adj);
const vi sequence {1,0,1,0,0,1};
queue<tuple<int, int, int>> q;
for (auto [nxt, edge] : adj[0]) {
X[edge] = sequence[0];
q.emplace(nxt, 1, sequence[0]);
}
DBG("Mark");
while (!q.empty()) {
auto [crt, counter, prv] = q.front();
q.pop();
DBG(crt, counter);
if (adj[crt].size() == 1) continue;
if (adj[crt].size() == 2) {
for (auto [nxt, edge] : adj[crt]) {
if (X[edge] == -1) {
X[edge] = sequence[counter % sequence.size()];
q.emplace(nxt, counter+1, X[edge]);
}
}
} else {
for (auto [nxt, edge] : adj[crt]) {
if (X[edge] == -1) {
X[edge] = !prv;
q.emplace(nxt, X[edge]? 1: 2, X[edge]);
}
}
}
}
DBG(X);
return X;
}
} // namespace
std::vector<int> Mark(int N, int M, int A, int B,
std::vector<int> U, std::vector<int> V) {
if (N == M+1) return Mark2d(N, U, V);
while (1);
}
/*
7 6 2 6 3
6 5
5 0
0 1
1 2
2 3
3 4
12 11 2 6 4
6 5
5 0
0 1
1 2
2 3
3 4
4 7
7 8
8 9
9 10
10 11
19 18 2 12 11
0 2
1 2
2 3
3 4
4 5
4 6
6 7
3 8
8 9
8 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
*/
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using i64 = int64_t;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;
constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();
#define RANGE(x) begin(x), end(x)
template <typename... T>
void DBG(T&&... args) {
//((cerr << args << ' '), ...) << '\n';
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
out << '{';
for (size_t i = 0; i < vec.size()-1; ++i)
out << vec[i] << ", ";
out << vec.back() << '}';
return out;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
out << '(' << pr.first << ", " << pr.second << ')';
return out;
}
namespace {
int A, B;
bool found = false, first = true;
string current_path;
const string incr_way = "1101001101001";
const string decr_way = "1100101100101";
int prv = -1;
// 0 1
int move2d(int a, int b) {
if (first) {
DBG("FIRST!");
int r;
if (a+b == 1) {
DBG("FOUND! by endpoint");
found = true;
r = a? 0: 1;
} else if (a+b==2) {
if (a == 2) {
current_path = "00";
r = 0;
} else if (b == 2) {
current_path = "11";
r = 1;
} else {
current_path = "10";
r = 0;
}
} else {
DBG("FOUND! by intersection");
r=-2;// not possible!
if (a == 1) r = 0;
if (b == 1) r = 1;
}
DBG("DONE FIRST:", r);
first = false;
return r;
}
if (a+b == 0) { // end point
DBG("FOUND! by endpoint");
found = true;
return -1;
}
if (a+b >= 2) {
DBG("FOUND! by intersection");
found = true;
if (a == 0 || b == 0) return -1;
if (prv) b++;
else a++;
if (a == 1) return 0;
if (b == 1) return 1;
return -2; // not possible!
}
if (!found) {
current_path += a? '0': '1';
int correct = decr_way.find(current_path) != string::npos;
int wrong = incr_way.find(current_path) != string::npos;
DBG(current_path);
found = true;
if (correct + wrong == 2) found = false;
else if (wrong) {
DBG("FOUND! by wrong direction");
return -1;
}
if (found) DBG("FOUND! by good direction");
}
if (a) return 0;
else return 1;
}
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
}
int Move(std::vector<int> y) {
return prv = move2d(y[0], y[1]);
}
