#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
static vector<int> g[MAXN];
static set<int> comp[MAXN], leaves[MAXN];
static short cor[MAXN];
static queue<int> qu;
static int n, m;
static ll x;
static void predfs(int cur) {
comp[0].insert(cur);
cor[cur]=comp[0].size()-1;
short ok=0;
for(auto viz : g[cur]) {
if(cor[viz]!=-1) continue;
if(comp[0].size()<60) predfs(viz), ok++;
else if(cor[viz]==-1) qu.push(viz);
}
if(!ok||(cur==0&&ok==1)) leaves[0].insert(cur);
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
n=N; m=M; x=X; for(int i=0; i<m; i++) g[A[i]].push_back(B[i]), g[B[i]].push_back(A[i]);
memset(cor, -1, sizeof(cor)); predfs(0);
for(int i=1; i<n; i++) if(cor[i]!=-1) comp[i]=comp[0], leaves[i]=leaves[0];
while(qu.size()) {
int cur=qu.front(); qu.pop();
if(comp[cur].size()) continue;
// printf("resolvendo %d\n", cur);
for(auto viz : g[cur]) {
if(cor[viz]==-1) qu.push(viz);
else if(comp[cur].empty()) {
comp[cur]=comp[viz]; comp[cur].insert(cur);
leaves[cur]=leaves[viz]; leaves[cur].insert(cur);
int leaf; for(auto cara : leaves[viz]) if(cara!=viz) leaf=cara;
int nleaf; for(auto cara : g[leaf]) if(comp[viz].find(cara)!=comp[viz].end()) nleaf=cara;
// printf("leaf= %d nleaf= %d\n", leaf, nleaf);
cor[cur]=cor[leaf];
comp[cur].erase(leaf);
leaves[cur].erase(viz);
leaves[cur].erase(leaf);
leaves[cur].insert(nleaf);
}
}
}
// for(auto cur : leaves[61]) printf("%d ", cur);
for(int i=0; i<n; i++) {
ll mask=0;
for(auto cara : comp[i]) mask|=(1LL<<cor[cara]);
if(mask!=(1LL<<60)-1) printf("erro!! %d >> %lld\n", i, mask);
}
for(int i = 0; i < N; i++) MessageBoard(i, (bool)(x&(1LL<<cor[i])));
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
vector<int> g[MAXN];
set<int> comp[MAXN], leaves[MAXN];
short cor[MAXN];
queue<int> qu;
int n, m;
ll x, respf, mask;
void predfs(int cur) {
comp[0].insert(cur);
cor[cur]=comp[0].size()-1;
short ok=0;
for(auto viz : g[cur]) {
if(cor[viz]!=-1) continue;
if(comp[0].size()<60) predfs(viz), ok++;
else if(cor[viz]==-1) qu.push(viz);
}
if(!ok||(cur==0&&ok==1)) leaves[0].insert(cur);
}
void resolve(int cur) {
// printf("resolve %d\n", cur);
for(auto viz : g[cur]) {
if(mask&(1LL<<cor[viz])) continue;
if(comp[cur].find(viz)==comp[cur].end()) continue;
if(Move(viz)) respf|=(1LL<<cor[viz]);
mask|=(1LL<<cor[viz]);
resolve(viz);
Move(cur);
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
n=N; m=M; for(int i=0; i<m; i++) g[A[i]].push_back(B[i]), g[B[i]].push_back(A[i]);
memset(cor, -1, sizeof(cor)); predfs(0);
for(int i=1; i<n; i++) if(cor[i]!=-1) comp[i]=comp[0], leaves[i]=leaves[0];
while(qu.size()) {
int cur=qu.front(); qu.pop();
if(comp[cur].size()) continue;
for(auto viz : g[cur]) {
if(cor[viz]==-1) qu.push(viz);
else if(comp[cur].empty()) {
comp[cur]=comp[viz]; comp[cur].insert(cur);
leaves[cur]=leaves[viz]; leaves[cur].insert(cur);
int leaf; for(auto cara : leaves[viz]) if(cara!=viz) leaf=cara;
int nleaf; for(auto cara : g[leaf]) if(comp[viz].find(cara)!=comp[viz].end()) nleaf=cara;
cor[cur]=cor[leaf];
comp[cur].erase(leaf);
leaves[cur].erase(viz);
leaves[cur].erase(leaf);
leaves[cur].insert(nleaf);
}
}
}
if(V) respf|=(1LL<<cor[P]);
mask|=(1LL<<cor[P]);
resolve(P);
// printf("mask= %lld // respf= %lld\n", mask, respf);
return respf;
}
