#include "Joi.h"
#include <iostream>
#include <vector>
using namespace std;
int vis_Joi[10010], ord_Joi[10010], cnt_Joi;
vector<int> edge_Joi[10010];
void dfs_Joi(int u) {
vis_Joi[u] = 1;
ord_Joi[u] = cnt_Joi++;
for (int i = 0; i < edge_Joi[u].size(); i++) if (!vis_Joi[edge_Joi[u][i]]) dfs_Joi(edge_Joi[u][i]);
}
void Joi(int n, int m, int A[], int B[], long long X, int T) {
for (int i = 0; i < m; i++) {
edge_Joi[A[i]].push_back(B[i]);
edge_Joi[B[i]].push_back(A[i]);
}
dfs_Joi(0);
for (int i = 0; i < n; i++) MessageBoard(i,((X>>(ord_Joi[i]%60)))%2);
}
#include "Ioi.h"
#include <iostream>
#include <vector>
using namespace std;
long long vis[10010], ord[10010], cnt, p[10010], ans[70], hv[10010][70], ok[70], ord2[10010], uu;
vector<long long> edge[10010], adj[10010], path, tmp, viss;
bool can, done;
void dfs(int u) {
vis[u] = 1;
ord[u] = cnt++;
hv[u][ord[u]%60] = 1;
for (int i = 0; i < edge[u].size(); i++) {
if (!vis[edge[u][i]]) {
adj[u].push_back(edge[u][i]);
p[edge[u][i]] = u;
dfs(edge[u][i]);
for (int j = 0; j < 60; j++) hv[u][j] |= hv[edge[u][i]][j];
}
}
ord2[u] = cnt;
}
bool check(int u) {
for (int i = 0; i < 60; i++) if (!hv[u][i]) return 0;
return 1;
}
void dfs1(int u) {
for (int i = 0; i < 60; i++) if (!ok[i] && hv[u][i]) goto skip;
return;
skip:;
ok[ord[u]%60] = vis[u] = 1;
for (int i = 0; i < adj[u].size(); i++) dfs1(adj[u][i]);
}
void dfs2(int u, int lst, int need_check) {
if (!can) return;
if (need_check && (u != uu) && (ord[u] <= ord[lst]) && (ord2[lst] <= ord2[u])) {
can = 0;
return;
}
tmp.push_back(u);
vis[u] = 0;
for (int i = 0; i < adj[u].size(); i++) if ((vis[adj[u][i]]) && (!((ord[adj[u][i]] <= ord[lst]) && (ord2[lst] <= ord2[adj[u][i]])))) dfs2(adj[u][i],lst,0);
for (int i = 0; i < adj[u].size(); i++) if ((vis[adj[u][i]]) && ((ord[adj[u][i]] <= ord[lst]) && (ord2[lst] <= ord2[adj[u][i]]))) dfs2(adj[u][i],lst,0);
if (u == lst) done = 1;
if (!done) tmp.push_back(u);
if ((p[u] != -1) && (vis[p[u]])) dfs2(p[u],lst,1);
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
for (int i = 0; i < m; i++) {
edge[A[i]].push_back(B[i]);
edge[B[i]].push_back(A[i]);
}
for (int i = 0; i < n; i++) p[i] = -1;
dfs(0);
int u = P;
for (int i = 0; i < n; i++) vis[i] = 0;
ok[ord[u]%60] = vis[u] = 1;
while (!check(u)) u = p[u], ok[ord[u]%60] = vis[u] = 1;
uu = u;
dfs1(u);
for (int i = 0; i < n; i++) if (vis[i]) viss.push_back(i);
for (int i = 0; i < n; i++) {
if (vis[i]) {
cnt = 0;
for (int j = 0; j < adj[i].size(); j++) cnt += vis[adj[i][j]];
if (cnt != 1) continue;
tmp.clear();
can = 1; done = 0;
dfs2(P,i,1);
for (int j = 0; j < viss.size(); j++) vis[viss[j]] = 1;
if (can && (path.empty() || (tmp.size() < path.size()))) path = tmp;
}
}
u = P;
ans[ord[u]%60] = V;
for (int i = 0; i < path.size(); i++) {
if (u == path[i]) continue;
u = path[i];
ans[ord[u]%60] = Move(u);
}
long long x = 0;
for (int i = 0; i < 60; i++) x += (ans[i]<<i);
return x;
}
