#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
namespace JOI {
const int MAX_N = 1e4;
const int MAX_M = 2e4;
const int K = 60;
int n, m;
bool isTreeDeep = true;
bool vis[MAX_N], isSpecial[MAX_N], message[MAX_N];
int depth[MAX_N], maxDepth[MAX_N], deepestSon[MAX_N], parent[MAX_N];
vector<int> specials;
pair<int, int> edges[MAX_M];
vector<int> adj[MAX_N];
void getDepths( int u ) {
vis[u] = true;
maxDepth[u] = depth[u];
for ( int v: adj[u] ) {
if ( vis[v] )
continue;
depth[v] = depth[u] + 1;
parent[v] = u;
getDepths( v );
if ( maxDepth[v] > maxDepth[u] ) {
deepestSon[u] = v;
maxDepth[u] = maxDepth[v];
}
}
}
void getSpecials( int u ) {
vis[u] = true;
if ( specials.size() == K )
return;
if ( !isSpecial[u] ) {
specials.push_back( u );
isSpecial[u] = true;
}
for ( int v: adj[u] ) {
if ( vis[v] )
continue;
getSpecials( v );
}
}
void proccessTree( int N, int M, int A[], int B[] ) {
n = N;
m = M;
for ( int i = 0; i < m; i++ )
edges[i] = { A[i], B[i] };
sort( edges, edges + m );
for ( int i = 0; i < m; i++ ) {
adj[edges[i].first].push_back( edges[i].second );
adj[edges[i].second].push_back( edges[i].first );
}
getDepths( 0 );
int deepestVertex = 0;
for ( int v = 1; v < n; v++ ) {
if ( depth[v] > depth[deepestVertex] )
deepestVertex = v;
}
if ( depth[deepestVertex] < K - 1 ) {
isTreeDeep = false;
for ( int v = 0; v < n; v++ )
vis[v] = false;
int v = deepestVertex;
while ( v != 0 ) {
isSpecial[v] = true;
specials.push_back( v );
v = parent[v];
}
getSpecials( 0 );
assert( specials.size() >= K );
}
}
}
using namespace JOI;
void Joi( int N, int M, int A[], int B[], long long x, int T ) {
proccessTree( N, M, A, B );
if ( isTreeDeep ) {
//printf( "DEEP TREE\n" );
for ( int v = 0; v < n; v++ )
message[v] = ((x >> (K - 1 - depth[v] % K)) & 1);
} else {
//printf( "NOT DEEP TREE\n" );
for ( int i = 0; i < K; i++ )
message[specials[i]] = ((x >> i) & 1);
}
for ( int v = 0; v < n; v++ )
MessageBoard( v, message[v] );
/*for ( int v = 0; v < n; v++ )
printf( "%d %d\n", v, message[v] );*/
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
namespace IOI {
const int MAX_N = 1e4;
const int MAX_M = 2e4;
const int K = 60;
int n, m;
bool isTreeDeep = true;
int deepestVertex;
bool vis[MAX_N], isSpecial[MAX_N], message[MAX_N];
int depth[MAX_N], maxDepth[MAX_N], deepestSon[MAX_N], parent[MAX_N];
vector<int> specials;
pair<int, int> edges[MAX_M];
vector<int> adj[MAX_N];
void getDepths( int u ) {
vis[u] = true;
maxDepth[u] = depth[u];
for ( int v: adj[u] ) {
if ( vis[v] )
continue;
depth[v] = depth[u] + 1;
parent[v] = u;
getDepths( v );
if ( maxDepth[v] > maxDepth[u] ) {
deepestSon[u] = v;
maxDepth[u] = maxDepth[v];
}
}
}
void getSpecials( int u ) {
vis[u] = true;
if ( specials.size() == K )
return;
if ( !isSpecial[u] ) {
specials.push_back( u );
isSpecial[u] = true;
}
for ( int v: adj[u] ) {
if ( vis[v] )
continue;
getSpecials( v );
}
}
void proccessTree( int N, int M, int A[], int B[] ) {
n = N;
m = M;
for ( int i = 0; i < m; i++ )
edges[i] = { A[i], B[i] };
sort( edges, edges + m );
for ( int i = 0; i < m; i++ ) {
adj[edges[i].first].push_back( edges[i].second );
adj[edges[i].second].push_back( edges[i].first );
}
getDepths( 0 );
deepestVertex = 0;
for ( int v = 1; v < n; v++ ) {
if ( depth[v] > depth[deepestVertex] )
deepestVertex = v;
}
if ( depth[deepestVertex] < K - 1 ) {
isTreeDeep = false;
for ( int v = 0; v < n; v++ )
vis[v] = false;
int v = deepestVertex;
while ( v != 0 ) {
isSpecial[v] = true;
specials.push_back( v );
v = parent[v];
}
getSpecials( 0 );
assert( specials.size() >= K );
}
}
}
using namespace IOI;
int specialsDiscovered = 0;
void discoverSpecials( int u ) {
specialsDiscovered++;
vis[u] = true;
int lastSon = -1, maxx = 0;
for ( int v: adj[u] ) {
if ( vis[v] || !isSpecial[v] )
continue;
if ( maxDepth[v] > maxx ) {
lastSon = v;
maxx = maxDepth[v];
}
}
for ( int v: adj[u] ) {
if ( vis[v] || !isSpecial[v] || v == lastSon )
continue;
int b = Move( v );
message[v] = b;
discoverSpecials( v );
Move( u );
}
if ( lastSon != -1 ) {
int v = lastSon;
int b = Move( v );
message[v] = b;
discoverSpecials( v );
if ( specialsDiscovered < K )
Move( u );
}
}
long long Ioi( int N, int M, int A[], int B[], int P, int V, int T ) {
proccessTree( N, M, A, B );
int v = P, b = V;
long long x = 0;
if ( isTreeDeep ) {
//printf( "DEEP TREE\n" );
if ( depth[v] >= K ) {
x += ((long long)b << (K - 1 - depth[v] % K));
for ( int i = 0; i < K - 1; i++ ) {
v = parent[v];
b = Move( v );
x += ((long long)b << (K - 1 - depth[v] % K));
}
} else {
message[v] = b;
while ( v != 0 ) {
v = parent[v];
b = Move( v );
message[v] = b;
}
x += ((long long)b << (K - 1 - depth[v] % K));
for ( int i = 0; i < K - 1; i++ ) {
v = deepestSon[v];
b = Move( v );
x += ((long long)b << (K - 1 - depth[v] % K));
}
}
} else {
//printf( "NOT DEPP TREE\n" );
message[v] = b;
while ( v != 0 ) {
v = parent[v];
b = Move( v );
message[v] = b;
}
for ( int v = 0; v < n; v++ )
vis[v] = false;
specialsDiscovered = 0;
discoverSpecials( 0 );
for ( int i = 0; i < specials.size(); i++ )
x += ((long long)message[specials[i]] << i);
}
/*for ( int v = 0; v < n; v++ )
printf( "%d %d\n", v, message[v] );
printf( "%lld\n", x );*/
return x;
}
