#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
//MessageBoard(index,val)
struct DSU{
vector<int>e;
void init(int n){
e=vector<int>(n,-1);
}
int get(int x){
return e[x]<0?x:e[x]=get(e[x]);
}
bool unite(int x, int y){
x=get(x); y=get(y);
if(x==y) return 1;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y];
e[y]=x;
return 0;
}
};
int visited[10005];
int bit[10005];
vector<int>adj[10005];
set<int>se;
vector<int>storage;
int lst=0;
void dfs(int index, int sz){
if((int)storage.size()==sz) return;
visited[index]=lst+1;
storage.push_back(index);
if(lst==0) bit[index]=storage.size()-1;
se.erase(bit[index]);
if((int)storage.size()==sz) return;
for(auto it:adj[index]){
if(visited[it]!=lst) continue;
dfs(it,sz);
}
}
void Joi(int32_t n, int32_t m, int32_t a[], int32_t b[], long long val, int32_t t){
DSU dsu;
dsu.init(n+5);
for(int x=0;x<m;x++){
if(dsu.unite(a[x],b[x])) continue;
adj[a[x]].push_back(b[x]);
adj[b[x]].push_back(a[x]);
}
queue<pii>q;
q.push({0,0});
while(!q.empty()){
pii cur=q.front();
se.clear();
storage.clear();
for(int y=0;y<60;y++) se.insert(y);
dfs(cur.first,cur.second==0?60:59);
visited[cur.second]=lst+1;
if(cur.second!=0)bit[cur.second]=*se.begin();
for(auto it:adj[cur.second]){
if(visited[it]==0){
q.push({cur.second,it});
}
}
lst++;
}
for(int x=0;x<n;x++){
int a=0;
if(val&(1LL<<bit[x])) a=1;
MessageBoard(x,a);
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
//MessageBoard(index,val)
struct DSU{
vector<int>e;
void init(int n){
e=vector<int>(n,-1);
}
int get(int x){
return e[x]<0?x:e[x]=get(e[x]);
}
bool unite(int x, int y){
x=get(x); y=get(y);
if(x==y) return 1;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y];
e[y]=x;
return 0;
}
};
int visited[10005];
int bit[10005];
vector<int>adj[10005];
set<int>se;
vector<int>storage;
vector<int>path;
int lst=0;
void dfs(int index, int sz, int par){
if((int)storage.size()==sz) return;
if(par!=-1)path.push_back(index);
visited[index]=lst+1;
storage.push_back(index);
if(lst==0) bit[index]=storage.size()-1;
se.erase(bit[index]);
if((int)storage.size()==sz) return;
for(auto it:adj[index]){
if(visited[it]!=lst) continue;
dfs(it,sz,index);
}
if(par!=-1) path.push_back(par);
}
long long Ioi(int32_t n, int32_t m, int32_t a[], int32_t b[], int32_t p, int32_t v, int32_t t){
DSU dsu;
dsu.init(n+5);
for(int x=0;x<m;x++){
if(dsu.unite(a[x],b[x])) continue;
adj[a[x]].push_back(b[x]);
adj[b[x]].push_back(a[x]);
}
queue<pii>q;
q.push({0,0});
int ret=0;
while(!q.empty()){
pii cur=q.front();
se.clear();
storage.clear();
path.clear();
for(int y=0;y<60;y++) se.insert(y);
dfs(cur.first,cur.second==0?60:59,-1);
visited[cur.second]=lst+1;
if(cur.second!=0){
bit[cur.second]=*se.begin();
storage.push_back(cur.second);
}
//check
bool amos=false;
for(auto it:storage){
if(it==p) amos=true;
}
if(amos){
int arr[60];
for(auto it:path){
int a=Move(it);
arr[bit[it]]=a;
}
for(int y=0;y<60;y++){
ret+=arr[y]*(1LL<<y);
}
return ret;
}
for(auto it:adj[cur.second]){
if(visited[it]==0){
q.push({cur.second,it});
}
}
lst++;
}
return 0;
}
