#define _CRT_SECURE_NO_WARNINGS
#define SUBMIT 1
#include <cstdio>
#include <cstdlib>
#include <set>
#include <algorithm>
#include<vector>
#include<iostream>
#define int long long
using namespace std;
//grader
#if (SUBMIT == 0)
#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000
void Joi(int32_t N, int32_t M, int32_t A[], int32_t B[], long long X, int32_t T);
long long Ioi(int32_t N, int32_t M, int32_t A[], int32_t B[], int32_t P, int32_t V, int32_t T);
static int32_t N, M, A[MMAX], B[MMAX], P, T;
static long long X;
static int given_msg[NMAX];
static int pos, n_move;
static set<pair<int, int> > edges;
void WrongAnswer(int e)
{
printf("Wrong Answer[%d]\n", e);
exit(1);
}
void MessageBoard(int attr, int msg)
{
if (!(0 <= attr && attr <= N - 1)) {
WrongAnswer(1);
}
if (given_msg[attr] != -1) {
WrongAnswer(2);
}
if (!(msg == 0 || msg == 1)) {
WrongAnswer(3);
}
given_msg[attr] = msg;
}
int Move(int dest)
{
if (!(0 <= dest && dest <= N - 1)) {
WrongAnswer(6);
}
if (!edges.count({ pos, dest })) {
WrongAnswer(7);
}
++n_move;
if (n_move > MOVEMAX) {
WrongAnswer(8);
}
pos = dest;
return given_msg[pos];
}
int32_t main(void)
{
int i;
long long max_code;
scanf("%d%d%lld%d%d", &N, &M, &X, &P, &T);
for (int i = 0; i < M; ++i) {
scanf("%d%d", &(A[i]), &(B[i]));
edges.insert({ A[i], B[i] });
edges.insert({ B[i], A[i] });
}
for (int i = 0; i < N; ++i) {
given_msg[i] = -1;
}
Joi((int32_t)N, (int32_t)M, A, B, X, (int32_t)T);
for (i = 0; i < N; ++i) {
if (given_msg[i] == -1) {
WrongAnswer(4);
}
}
n_move = 0;
pos = P;
long long answer = Ioi(N, M, A, B, P, given_msg[P], T);
if (answer != X) {
WrongAnswer(5);
}
printf("Accepted : #move=%d\n", n_move);
return 0;
}
#endif
//common code
vector<int> g[10005], res;
vector<bool> vis, ans;
void dfs(int node) {
vis[node] = 1, res.push_back(node);
if (res.size() < 60)
for (auto x : g[node])
if ((!vis[x]) && (res.size() < 60))
dfs(x);
}
// joi
#if SUBMIT <= 1
#if SUBMIT == 1
void Joi(int32_t N, int32_t M, int32_t A[], int32_t B[], long long X, int32_t T);
void MessageBoard(int32_t attr, int32_t msg);
#endif
void Joi(int32_t n, int32_t m, int32_t a[], int32_t b[], long long r, int32_t t) {
ans.assign(n, 0);
if (t == 3)
for (int i = 0; i < n; ++i)
ans[i] = ((r & (1ll << (i % 60ll))) > 0ll);
else {
for (int i = 0; i < m; ++i)
g[(int)a[i]].push_back((int)b[i]),
g[(int)b[i]].push_back((int)a[i]);
vis.assign(n, 0), dfs(0);
int cur = 0;
for (auto x : res) ans[x] = ((r & (1ll << cur)) > 0), cur += 1;
}
for (int i = 0; i < n; ++i) MessageBoard((int32_t)i, (int32_t)ans[i]);
}
#endif
//ioi
#if SUBMIT % 2 == 0
#if SUBMIT == 2
long long Ioi(int32_t N, int32_t M, int32_t A[], int32_t B[], int32_t P, int32_t V, int32_t T);
int Move(int32_t dest);
#endif
vector<int> uni;
bool dfs2(int node) {
if (node == 0) return 1;
vis[node] = 1, res.push_back(node);
for (auto x : g[node])
if (!vis[x]) if (dfs2(x)) return 1;
res.pop_back(); return 0;
}
void dfs3(int node) {
vis[node] = 1; res.push_back(node);
uni.push_back(node);
if (uni.size() < 60)
for (auto x : g[node])
if ((!vis[x]) && (uni.size() < 60))
dfs3(x), res.push_back(node);
}
long long Ioi(int32_t n, int32_t m, int32_t a[], int32_t b[], int32_t p, int32_t v, int32_t t) {
for (int i = 0; i < m; ++i)
g[(int)a[i]].push_back((int)b[i]),
g[(int)b[i]].push_back((int)a[i]);
int s = 0; res.clear();
if (t == 3) {
int i = p;
for (; (((i + 1) % 60) != 0); --i)
res.push_back(i);
if (i >= 0) {
int j = i;
for (; (((i + 1) % 60) != 0) || (i == j); --i)
res.push_back(i);
}
s = i + 1;
for (i+=2; (i % 60); ++i)
res.push_back(i);
ans.clear();
}
else { ans.clear(); res.clear(); vis.assign(n, 0); dfs2(p); vis.assign(n, 0); dfs3(0); }
bool f = 0;
vector<bool> done(n);
for (int i = 0; i < res.size(); ++i) {
auto x = res[i];
f = (f || (x == s));
if (f && (!done[x]))
if (i == 0) ans.push_back(v), done[x] = 1;
else ans.push_back(Move((int32_t)x)), done[x] = 1;
else if (i) Move(x);
}
int val = 0;
for (int i = 0; i < ans.size(); ++i)
val += (ans[i] * (1ll << i));
return val;
}
#endif
#define _CRT_SECURE_NO_WARNINGS
#define SUBMIT 2
#include <cstdio>
#include <cstdlib>
#include <set>
#include <algorithm>
#include<vector>
#include<iostream>
#define int long long
using namespace std;
//grader
#if (SUBMIT == 0)
#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000
void Joi(int32_t N, int32_t M, int32_t A[], int32_t B[], long long X, int32_t T);
long long Ioi(int32_t N, int32_t M, int32_t A[], int32_t B[], int32_t P, int32_t V, int32_t T);
static int32_t N, M, A[MMAX], B[MMAX], P, T;
static long long X;
static int given_msg[NMAX];
static int pos, n_move;
static set<pair<int, int> > edges;
void WrongAnswer(int e)
{
printf("Wrong Answer[%d]\n", e);
exit(1);
}
void MessageBoard(int attr, int msg)
{
if (!(0 <= attr && attr <= N - 1)) {
WrongAnswer(1);
}
if (given_msg[attr] != -1) {
WrongAnswer(2);
}
if (!(msg == 0 || msg == 1)) {
WrongAnswer(3);
}
given_msg[attr] = msg;
}
int Move(int dest)
{
if (!(0 <= dest && dest <= N - 1)) {
WrongAnswer(6);
}
if (!edges.count({ pos, dest })) {
WrongAnswer(7);
}
++n_move;
if (n_move > MOVEMAX) {
WrongAnswer(8);
}
pos = dest;
return given_msg[pos];
}
int32_t main(void)
{
int i;
long long max_code;
scanf("%d%d%lld%d%d", &N, &M, &X, &P, &T);
for (int i = 0; i < M; ++i) {
scanf("%d%d", &(A[i]), &(B[i]));
edges.insert({ A[i], B[i] });
edges.insert({ B[i], A[i] });
}
for (int i = 0; i < N; ++i) {
given_msg[i] = -1;
}
Joi((int32_t)N, (int32_t)M, A, B, X, (int32_t)T);
for (i = 0; i < N; ++i) {
if (given_msg[i] == -1) {
WrongAnswer(4);
}
}
n_move = 0;
pos = P;
long long answer = Ioi(N, M, A, B, P, given_msg[P], T);
if (answer != X) {
WrongAnswer(5);
}
printf("Accepted : #move=%d\n", n_move);
return 0;
}
#endif
//common code
vector<int> g[10005], res;
vector<bool> vis, ans;
void dfs(int node) {
vis[node] = 1, res.push_back(node);
if (res.size() < 60)
for (auto x : g[node])
if ((!vis[x]) && (res.size() < 60))
dfs(x);
}
// joi
#if SUBMIT <= 1
#if SUBMIT == 1
void Joi(int32_t N, int32_t M, int32_t A[], int32_t B[], long long X, int32_t T);
void MessageBoard(int32_t attr, int32_t msg);
#endif
void Joi(int32_t n, int32_t m, int32_t a[], int32_t b[], long long r, int32_t t) {
ans.assign(n, 0);
if (t == 3)
for (int i = 0; i < n; ++i)
ans[i] = ((r & (1ll << (i % 60ll))) > 0ll);
else {
for (int i = 0; i < m; ++i)
g[(int)a[i]].push_back((int)b[i]),
g[(int)b[i]].push_back((int)a[i]);
vis.assign(n, 0), dfs(0);
int cur = 0;
for (auto x : res) ans[x] = ((r & (1ll << cur)) > 0), cur += 1;
}
for (int i = 0; i < n; ++i) MessageBoard((int32_t)i, (int32_t)ans[i]);
}
#endif
//ioi
#if SUBMIT % 2 == 0
#if SUBMIT == 2
long long Ioi(int32_t N, int32_t M, int32_t A[], int32_t B[], int32_t P, int32_t V, int32_t T);
int Move(int32_t dest);
#endif
vector<int> uni;
bool dfs2(int node) {
if (node == 0) return 1;
vis[node] = 1, res.push_back(node);
for (auto x : g[node])
if (!vis[x]) if (dfs2(x)) return 1;
res.pop_back(); return 0;
}
void dfs3(int node) {
vis[node] = 1; res.push_back(node);
uni.push_back(node);
if (uni.size() < 60)
for (auto x : g[node])
if ((!vis[x]) && (uni.size() < 60))
dfs3(x), res.push_back(node);
}
long long Ioi(int32_t n, int32_t m, int32_t a[], int32_t b[], int32_t p, int32_t v, int32_t t) {
for (int i = 0; i < m; ++i)
g[(int)a[i]].push_back((int)b[i]),
g[(int)b[i]].push_back((int)a[i]);
int s = 0; res.clear();
if (t == 3) {
int i = p;
for (; (((i + 1) % 60) != 0); --i)
res.push_back(i);
if (i >= 0) {
int j = i;
for (; (((i + 1) % 60) != 0) || (i == j); --i)
res.push_back(i);
}
s = i + 1;
for (i+=2; (i % 60); ++i)
res.push_back(i);
ans.clear();
}
else { ans.clear(); res.clear(); vis.assign(n, 0); dfs2(p); vis.assign(n, 0); dfs3(0); }
bool f = 0;
vector<bool> done(n);
for (int i = 0; i < res.size(); ++i) {
auto x = res[i];
f = (f || (x == s));
if (f && (!done[x]))
if (i == 0) ans.push_back(v), done[x] = 1;
else ans.push_back(Move((int32_t)x)), done[x] = 1;
else if (i) Move(x);
}
int val = 0;
for (int i = 0; i < ans.size(); ++i)
val += (ans[i] * (1ll << i));
return val;
}
#endif
