#include<bits/stdc++.h>
#define ll long long
#include "Joi.h"
#include "Ioi.h"
using namespace std;
int rod[10005],vel[10005],koji[10005],ostalo;
ll step[65];
bool orgst[10005],koristi[10005];
int N,K=60;
vector<int> stablo[10005],S,ubacen[10005];
int getp(int x){
if(rod[x]==x)
return x;
rod[x]=getp(rod[x]);
return rod[x];
}
bool spoj(int a,int b){
a=getp(a);
b=getp(b);
if(a==b)
return false;
if(vel[a]>vel[b])
rod[b]=a;
else{
rod[a]=b;
vel[b]=max(vel[a]+1,vel[b]);
}
return true;
}
void dfs(int gde,int pret){
if(ostalo==0)
return;
//cout<<gde<<" "<<ostalo<<endl;
S.push_back(gde);
ostalo--;
koji[gde]=ostalo;
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i]!=pret)
dfs(stablo[gde][i],gde);
return;
}
pair<int,int> najdalji(int gde,int pret,bool ex=false){
if(koristi[gde]==false and ex==false)
return {gde,0};
int d=0;
pair<int,int> ret={gde,1},pp;
for(int i=0;i<stablo[gde].size();i++){
if(stablo[gde][i]==pret)
continue;
pp=najdalji(stablo[gde][i],gde);
if(pp.second>d){
d=pp.second;
ret=pp;
ret.second++;
}
}
return ret;
}
void dfs2(int gde,int pret,vector<int> ust){
if(orgst[gde])
return;
for(int i=0;i<ust.size();i++)
koristi[ust[i]]=true;
pair<int,int> pp =najdalji(gde,gde,true);
int najd=pp.first;
// cout<<gde<<" "<<pret<<" najdalji "<<najd<<endl;
for(int i=0;i<ust.size();i++)
if(ust[i]==najd){
swap(ust[i],ust[ust.size()-1]);
ust.pop_back();
break;
}
ust.push_back(gde);
ubacen[gde]=ust;
koji[gde]=koji[najd];
koristi[najd]=false;
for(int i=0;i<ust.size();i++)
koristi[ust[i]]=false;
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i]!=pret)
dfs2(stablo[gde][i],gde,ust);
}
void init(int n,int M,int A[],int B[]){
N=n;
for(int i=0;i<N;i++){
stablo[i].clear();
ubacen[i].clear();
koristi[i]=0;
orgst[i]=0;
koji[i]=0;
rod[i]=i;
vel[i]=0;
}
for(int i=0;i<M;i++){
if(!spoj(A[i],B[i]))
continue;
stablo[A[i]].push_back(B[i]);
stablo[B[i]].push_back(A[i]);
}
/*cout<<"STABLO: "<<endl;
for(int i=0;i<N;i++){
cout<<i<<": ";
for(int j=0;j<stablo[i].size();j++)
cout<<stablo[i][j]<<" ";
cout<<endl;
}*/
ostalo=K;
dfs(0,0);
for(int i=0;i<S.size();i++){
orgst[S[i]]=true;
ubacen[S[i]]=S;
}
for(int i=0;i<S.size();i++){
for(int j=0;j<stablo[S[i]].size();j++)
dfs2(stablo[S[i]][j],S[i],S);
}
// for(int i=0;i<N;i++)
// cout<<i<<": "<<koji[i]<<endl;
// cout<<endl;
step[0]=1;
for(int i=1;i<=59;i++)
step[i]=step[i-1]<<1;
}
void Joi(int n, int M, int A[], int B[], long long X, int T) {
init(n,M,A,B);
for(int i=0;i<N;i++)
MessageBoard(i,(step[koji[i]]&X)!=0);
return;
}
#include<bits/stdc++.h>
#define ll long long
#include "Joi.h"
#include "Ioi.h"
using namespace std;
int rod[10005],vel[10005],koji[10005],ostalo;
ll step[65];
bool orgst[10005],koristi[10005];
int N,K=60;
vector<int> stablo[10005],S,ubacen[10005];
int getp(int x){
if(rod[x]==x)
return x;
rod[x]=getp(rod[x]);
return rod[x];
}
bool spoj(int a,int b){
a=getp(a);
b=getp(b);
if(a==b)
return false;
if(vel[a]>vel[b])
rod[b]=a;
else{
rod[a]=b;
vel[b]=max(vel[a]+1,vel[b]);
}
return true;
}
void dfs(int gde,int pret){
if(ostalo==0)
return;
//cout<<gde<<" "<<ostalo<<endl;
S.push_back(gde);
ostalo--;
koji[gde]=ostalo;
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i]!=pret)
dfs(stablo[gde][i],gde);
return;
}
pair<int,int> najdalji(int gde,int pret,bool ex=false){
if(koristi[gde]==false and ex==false)
return {gde,0};
int d=0;
pair<int,int> ret={gde,1},pp;
for(int i=0;i<stablo[gde].size();i++){
if(stablo[gde][i]==pret)
continue;
pp=najdalji(stablo[gde][i],gde);
if(pp.second>d){
d=pp.second;
ret=pp;
ret.second++;
}
}
return ret;
}
void dfs2(int gde,int pret,vector<int> ust){
if(orgst[gde])
return;
for(int i=0;i<ust.size();i++)
koristi[ust[i]]=true;
pair<int,int> pp =najdalji(gde,gde,true);
int najd=pp.first;
// cout<<gde<<" "<<pret<<" najdalji "<<najd<<endl;
for(int i=0;i<ust.size();i++)
if(ust[i]==najd){
swap(ust[i],ust[ust.size()-1]);
ust.pop_back();
break;
}
ust.push_back(gde);
ubacen[gde]=ust;
koji[gde]=koji[najd];
koristi[najd]=false;
for(int i=0;i<ust.size();i++)
koristi[ust[i]]=false;
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i]!=pret)
dfs2(stablo[gde][i],gde,ust);
}
void init(int n,int M,int A[],int B[]){
N=n;
for(int i=0;i<N;i++){
stablo[i].clear();
ubacen[i].clear();
koristi[i]=0;
orgst[i]=0;
koji[i]=0;
rod[i]=i;
vel[i]=0;
}
for(int i=0;i<M;i++){
if(!spoj(A[i],B[i]))
continue;
stablo[A[i]].push_back(B[i]);
stablo[B[i]].push_back(A[i]);
}
/*cout<<"STABLO: "<<endl;
for(int i=0;i<N;i++){
cout<<i<<": ";
for(int j=0;j<stablo[i].size();j++)
cout<<stablo[i][j]<<" ";
cout<<endl;
}*/
ostalo=K;
dfs(0,0);
for(int i=0;i<S.size();i++){
orgst[S[i]]=true;
ubacen[S[i]]=S;
}
for(int i=0;i<S.size();i++){
for(int j=0;j<stablo[S[i]].size();j++)
dfs2(stablo[S[i]][j],S[i],S);
}
// for(int i=0;i<N;i++)
// cout<<i<<": "<<koji[i]<<endl;
// cout<<endl;
step[0]=1;
for(int i=1;i<=59;i++)
step[i]=step[i-1]<<1;
}
int broj[10005];
int poz;
void dfs3(int gde,int pret){
if(!koristi[gde])
return;
//cout<<gde<<" "<<pret<<endl;
if(poz!=gde){
broj[gde]=Move(gde);
poz=gde;
}
for(int i=0;i<stablo[gde].size();i++){
if(stablo[gde][i]!=pret){
// cout<<"IDI U "<<stablo[gde][i]<<" IZ "<<gde<<endl;
dfs3(stablo[gde][i],gde);
}
if(poz!=gde){
broj[gde]=Move(gde);
poz=gde;
}
}
return;
}
long long Ioi(int n, int M, int A[], int B[], int P, int V, int T) {
init(n,M,A,B);
broj[P]=V;
poz=P;
for(int i=0;i<ubacen[P].size();i++)
koristi[ubacen[P][i]]=true;
dfs3(P,P);
ll res=0;
/* for(int i=0;i<N;i++)
cout<<i<<" stoji "<<broj[i]<<endl;
for(int i=0;i<ubacen[P].size();i++)
cout<<ubacen[P][i]<<" ";
cout<<endl;*/
for(int i=0;i<ubacen[P].size();i++){
res+=broj[ubacen[P][i]]*step[koji[ubacen[P][i]]];
//cout<<ubacen[P][i]<<" "<<res<<endl;
}
return res;
}
