#define _CRT_SECURE_NO_WARNINGS
#define SUBMIT 1
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <set>
#include<vector>
#include<iostream>
#include<algorithm>
#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
//-------------------------------------------------------------------------------------------------------
// code starts here
//common code
vector<int> g[200005];
vector<bool> vis;
vector<int> label(int n) {
queue<pair<int, int>> q; q.push({ 0, 0 });
vector<int> lb(n, -1); lb[0] = 0;
while (!q.empty()) {
auto f = q.front(); q.pop();
for (auto x : g[f.first])
if (lb[x] == -1) lb[x] = f.second + 1, q.push({ x, lb[x] });
}
return lb;
}
// 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
int dfsA(int node, int r, int c) {
vis[node] = 1; MessageBoard(node, ((r & (1ll << c)) > 0)); c += 1;
for (auto x : g[node])
if ((c < 60) && (!vis[x]))
c += dfsA(x, r, c);
return c;
}
void Joi(int32_t n, int32_t m, int32_t a[], int32_t b[], long long r, 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]);
vector<int> lab = label(n), res(n);
if ((*max_element(lab.begin(), lab.end()) < 59))
vis.assign(n, 0), dfsA(0, r, 0);
else {
for (int i = 0; i < n; ++i)
res[i] = ((r & (1ll << (int)(lab[i] % 60ll))) > 0ll);
for (int i = 0; i < n; ++i) MessageBoard(i, res[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> res;
int dfsB(int node, int c, int s) {
vis[node] = 1, c += 1;
if (node == s) res.push_back(0);
else res.push_back(Move(node));
for (auto x : g[node])
if ((c < 60) && (!vis[x]))
c += dfsB(x, c, s);
return c;
}
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]);
auto lab = label(n);
int cur = v, op = p;
while ((lab[p] % 60) != 0)
for(auto x: g[p])
if (lab[x] == (lab[p] - 1)) {
cur = Move(x); op = p = x; break;
}
if ((*max_element(lab.begin(), lab.end()) < 59))
res.clear(), vis.assign(n, 0), dfsB(p, 0, p);
else {
res = { p };
while (1) {
if ((p % 60) == 1) break;
int np = p;
for (auto x : g[p])
if (lab[x] == (lab[p] - 1)) {
res.push_back(x); p = x; break;
}
if (p == np) break;
}
if (res.size() != 60) {
p = op; res = { p };
while (1) {
if((p % 60) == 59) break;
for (auto x : g[p])
if (lab[x] == (lab[p] + 1)) {
res.push_back(x); p = x; break;
}
}
}
}
vector<pair<int, int>> val = { {op%60, cur} };
for (int i = 1; i < res.size(); ++i)
val.push_back({ res[i]%60, Move(res[i]) });
sort(val.begin(), val.end());
int ans = 0;
for (int i = 0; i < 60; ++i)
ans += (val[i].second * (1ll << i));
return ans;
}
#endif
#define _CRT_SECURE_NO_WARNINGS
#define SUBMIT 2
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <set>
#include<vector>
#include<iostream>
#include<algorithm>
#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
//-------------------------------------------------------------------------------------------------------
// code starts here
//common code
vector<int> g[200005];
vector<bool> vis;
vector<int> label(int n) {
queue<pair<int, int>> q; q.push({ 0, 0 });
vector<int> lb(n, -1); lb[0] = 0;
while (!q.empty()) {
auto f = q.front(); q.pop();
for (auto x : g[f.first])
if (lb[x] == -1) lb[x] = f.second + 1, q.push({ x, lb[x] });
}
return lb;
}
// 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
int dfsA(int node, int r, int c) {
vis[node] = 1; MessageBoard(node, ((r & (1ll << c)) > 0)); c += 1;
for (auto x : g[node])
if ((c < 60) && (!vis[x]))
c += dfsA(x, r, c);
return c;
}
void Joi(int32_t n, int32_t m, int32_t a[], int32_t b[], long long r, 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]);
vector<int> lab = label(n), res(n);
if ((*max_element(lab.begin(), lab.end()) < 59))
vis.assign(n, 0), dfsA(0, r, 0);
else {
for (int i = 0; i < n; ++i)
res[i] = ((r & (1ll << (int)(lab[i] % 60ll))) > 0ll);
for (int i = 0; i < n; ++i) MessageBoard(i, res[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> res;
int dfsB(int node, int c, int s) {
vis[node] = 1, c += 1;
if (node == s) res.push_back(0);
else res.push_back(Move(node));
for (auto x : g[node])
if ((c < 60) && (!vis[x]))
c += dfsB(x, c, s);
return c;
}
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]);
auto lab = label(n);
int cur = v, op = p;
while ((lab[p] % 60) != 0)
for(auto x: g[p])
if (lab[x] == (lab[p] - 1)) {
cur = Move(x); op = p = x; break;
}
if ((*max_element(lab.begin(), lab.end()) < 59))
res.clear(), vis.assign(n, 0), dfsB(p, 0, p);
else {
res = { p };
while (1) {
if ((p % 60) == 1) break;
int np = p;
for (auto x : g[p])
if (lab[x] == (lab[p] - 1)) {
res.push_back(x); p = x; break;
}
if (p == np) break;
}
if (res.size() != 60) {
p = op; res = { p };
while (1) {
if((p % 60) == 59) break;
for (auto x : g[p])
if (lab[x] == (lab[p] + 1)) {
res.push_back(x); p = x; break;
}
}
}
}
vector<pair<int, int>> val = { {op%60, cur} };
for (int i = 1; i < res.size(); ++i)
val.push_back({ res[i]%60, Move(res[i]) });
sort(val.begin(), val.end());
int ans = 0;
for (int i = 0; i < 60; ++i)
ans += (val[i].second * (1ll << i));
return ans;
}
#endif
