#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))
#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)
#define pb push_back
#define pf push_front
#define endl "\n"
#define oo (int)(998244353)
#define maxN 10005
#define l(s) s.length()
#define vi vector <int>
#define vii vector <ii>
#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)
#define EPS 1e-9
#define pi (acos(-1))
#define ll long long
vi Ke[maxN];
int g[maxN], Par[maxN];
vi ttt;
int FSet(int u) {
return g[u] == u ? u : g[u] = FSet(g[u]);
}
void USet(int u, int v) {
int fu = FSet(u), fv = FSet(v);
if (fu == fv) return;
g[fv] = fu;
Ke[u].pb(v);
Ke[v].pb(u);
}
void DFS(int u) {
ttt.pb(u);
for (int v : Ke[u]) if (v != Par[u]) {
Par[v] = u;
DFS(v);
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
fto(i, 0, N-1) g[i] = i;
fto(i, 0, M-1) USet(A[i], B[i]);
Par[0] = -1;
DFS(0);
int i = 0;
while (1) {
if (i + 59 >= N) {
fto(j, i, N-1) MessageBoard(ttt[j], 0);
break;
}
int ok = 1;
fto(j, i+1, i + 59) {
int ko = 0;
fto(k, i, j-1) if (Par[ttt[j]] == ttt[k]) {
ko = 1;
break;
}
if (ko == 0) {
ok = 0;
break;
}
}
if (!ok) {
MessageBoard(ttt[i], 0);
++i;
continue;
}
fto(j, 0, 59) MessageBoard(ttt[i+j], ((X&(1LL << j)) > 0));
i += 60;
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))
#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)
#define pb push_back
#define pf push_front
#define endl "\n"
#define oo (int)(998244353)
#define maxN 10005
#define l(s) s.length()
#define vi vector <int>
#define vii vector <ii>
#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)
#define EPS 1e-9
#define pi (acos(-1))
#define ll long long
int n, m, p;
vi ke[maxN];
int s[maxN], par[maxN];
int col[maxN], pos[maxN], id[maxN];
vi tt;
int fSet(int u) {
return s[u] == u ? u : s[u] = fSet(s[u]);
}
void uSet(int u, int v) {
int fu = fSet(u), fv = fSet(v);
if (fu == fv) return;
s[fv] = fu;
ke[u].pb(v);
ke[v].pb(u);
}
void dfs(int u) {
pos[u] = (int)(tt.size());
tt.pb(u);
for (int v : ke[u]) if (v != par[u]) {
par[v] = u;
dfs(v);
}
}
int moveto(int u) {
if (u == 0) {
int res = 0;
while (p) {
res = Move(par[p]);
p = par[p];
}
return res;
}
while (par[u] != p) {
Move(par[p]);
p = par[p];
}
int res = Move(u);
p = u;
return res;
}
ll Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
fto(i, 0, N-1) s[i] = i;
fto(i, 0, M-1) uSet(A[i], B[i]);
par[0] = -1;
dfs(0);
int i = 0, tme = 0;
while (1) {
if (i + 59 >= N) {
fto(j, i, N-1) col[tt[j]] = -1;
break;
}
int ok = 1;
fto(j, i+1, i + 59) {
int ko = 0;
fto(k, i, j-1) if (par[tt[j]] == tt[k]) {
ko = 1;
break;
}
if (ko == 0) {
ok = 0;
break;
}
}
if (!ok) {
col[tt[i]] = -1;
++i;
continue;
}
++tme;
fto(j, 0, 59) col[tt[i+j]] = 1, id[i+j] = tme;
i += 60;
}
while (col[P] == -1) {
V = Move(par[P]);
P = par[P];
}
vi cur;
fto(i, 0, N-1) if (id[i] == id[pos[P]]) cur.pb(tt[i]);
int now = 0;
fto(i, 0, 59) if (cur[i] == P) now = i;
p = P;
ll res = (1LL << now)*V;
fto(i, 1, 59) {
now = (now + 1)%60;
res += (1LL << now)*moveto(cur[now]);
}
return res;
}
