#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define INF 1000000001LL
#define POT (1LL<<23)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
os<<"{"<<p.ff<<", "<<p.ss<<"}";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{";
for (size_t i = 0; i < v.size(); ++i) {
if (i) os << ", ";
os << v[i];
}
os << "}";
return os;
}
template<ll MOD=998244353>
struct mint_t{
ll x;
mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
mint_t fp(ll y)const{
mint_t a=1,b=x;
while(y){
if(y&1)a*=b;
b*=b;
y/=2;
}
return a;
}
mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
ll x;
in>>x;
a=mint_t<MOD>(x);
return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
out<<a.x;
return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
if(b>a || a<0)return 0;
return fct[a]/fct[b]/fct[a-b];
}
int query(std::vector<int> x);
void answer(int a,int b);
bool dir[48][15007];
vii e;
vi g[10007],g2[10007],d[10007],g3[10007],g4[10007];
ll ak=0;
bool vs[10007];
ll lay[10007],sz[10007],dp[10007],dg[10007],nm[10007];
ll dfs(ll v,ll x,ll pop){
if(lay[v]!=x || vs[v])return 0;
vs[v]=1;
d[pop].pb(v);
sz[v]=1;
for(ll i : g2[v])sz[v]+=dfs(i,x,v);
return sz[v];
}
ll fnd(ll v,ll x){
for(ll i: d[v])if(sz[i]*2>x)return fnd(i,x);
return v;
}
void df2(ll v,ll x,ll y){
dp[v]=x;
for(ll i : d[v])df2(i,x+y,y);
}
ll mx=0;
void slv(vi v,ll it){
if(v.size()<2)return;
mx=max(mx,it+3);
for(ll i: v)lay[i]=ak,vs[i]=0,d[i].clear();
ll cent=fnd(v[0],dfs(v[0],ak,10006));
ak++;
for(ll i: v)lay[i]=ak,vs[i]=0,d[i].clear();
dfs(cent,ak,10006);
ll l=0,r=d[cent].size()-1,l1=0,l2=0;
while((l1+sz[d[cent][l]])*2<v.size())l1+=sz[d[cent][l++]];
while((l2+sz[d[cent][r]])*2<v.size())l2+=sz[d[cent][r--]];
l--;r++;
for(ll i=0;i<3;i++){
df2(cent,0,1);
if(i==0)for(ll j=0;j<=l;j++)df2(d[cent][j],-1,-1);
if(i==1)for(ll j=l+1;j<r;j++)df2(d[cent][j],-1,-1);
if(i==2)for(ll j=r;j<d[cent].size();j++)df2(d[cent][j],-1,-1);
for(ll j : v){
for(ll k : g3[j]){
if(lay[e[k].ss]!=ak)continue;
dir[it+i][k]=(pii{dp[e[k].ff],e[k].ff}>pii{dp[e[k].ss],e[k].ss});
}
}
}
dp[cent]=-1;
for(ll j=0;j<=l;j++)df2(d[cent][j],1,0);
for(ll j=l+1;j<r;j++)df2(d[cent][j],2,0);
for(ll j=r;j<d[cent].size();j++)df2(d[cent][j],3,0);
//cout<<"xd"<<flush;
for(ll j : v){
for(ll k : g3[j]){
if(lay[e[k].ss]!=ak)continue;
if(dp[e[k].ff]!=dp[e[k].ss]){
for(ll i=it+3;i<48;i++)dir[i][k]=(dp[e[k].ff]>dp[e[k].ss]);
}
}
}
//cout<<l<<" "<<r<<"\n";
ak++;
vi v2[3];
if(l)v2[0].pb(cent);
if(l+2<r)v2[1].pb(cent);
if(r!=d[cent].size()-1)v2[2].pb(cent);
for(ll i : v){
if(i!=cent)v2[dp[i]-1].pb(i);
}
//for(ll i=0;i<3;i++)cout<<v2[i]<<endl;cout<<endl;
for(ll i=0;i<3;i++){
slv(v2[i],it+3);
}
}
void solve(int n,int m,vector<int>u,vector<int>v){
for(ll i=0;i<m;i++){
g[u[i]].pb(v[i]);
g3[u[i]].pb(i);
e.pb({u[i],v[i]});
g2[u[i]].pb(v[i]);
g2[v[i]].pb(u[i]);
}
vi v2;
for(ll i=0;i<n;i++){
v2.pb(i);
}
slv(v2,0);
vector<int>zap;
while(mx--){
zap.clear();
for(ll j=0;j<m;j++){
zap.pb(dir[mx][j]);
}
if(query(zap)){
//cout<<zap<<endl;
for(ll i=0;i<m;i++){
if(zap[i])g4[v[i]].pb(u[i]),dg[u[i]]++;
else g4[u[i]].pb(v[i]),dg[v[i]]++;
}
break;
}
}
while(zap.empty())n++;
queue<ll>q;
for(ll i=0;i<n;i++){
if(dg[i]==0)q.push(i);
}
vi ord;
ak=0;
while(q.size()){
nm[q.front()]=ak++;
ord.pb(q.front());q.pop();
for(ll i : g4[ord.back()])if(--dg[i]==0)q.push(i);
}
ll l=1,r=n-1;
while(l!=r){
ll md=(l+r+1)/2;
vector<int>za;
for(ll i=0;i<m;i++){
za.pb((nm[e[i].ff]>=md || nm[e[i].ss]>=md)^zap[i]);
}
if(query(za))r=md-1;
else l=md;
}
ll kn=l;
l=0;r=n-2;
while(l!=r){
ll md=(l+r)/2;
vector<int>za;
for(ll i=0;i<m;i++){
za.pb((nm[e[i].ff]<=md || nm[e[i].ss]<=md)^zap[i]);
}
if(query(za))l=md+1;
else r=md;
}
answer(ord[l],ord[kn]);
}
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <vector>
namespace {
enum {
INVALID_X_LENGTH = 1,
INVALID_X_VALUE = 2,
QUERY_LIMIT_EXCEEDED = 3,
INVALID_A_VALUE = 4,
INVALID_B_VALUE = 5,
WRONG_ANSWER = 6,
ANSWER_TWICE = 7,
NO_ANSWER = 8,
};
const int QUERY_LIMIT = 300;
int QUERY_COUNT = 0;
int ANSWER_COUNT = 0;
int N, M, A, B;
std::vector<int> U, V;
std::vector<std::vector<std::pair<int, int>>> gg;
void wrong_answer(int code) {
printf("Wrong Answer [%d]\n", code);
exit(1);
}
} // namespace
int query(std::vector<int> x) {
QUERY_COUNT++;
if (QUERY_COUNT > QUERY_LIMIT) {
wrong_answer(QUERY_LIMIT_EXCEEDED);
}
if ((int)x.size() != M) {
wrong_answer(INVALID_X_LENGTH);
}
for (int c : x) {
if (c != 0 && c != 1) {
wrong_answer(INVALID_X_VALUE);
}
}
std::vector<int> q = {A};
std::vector<bool> visited(N);
visited[A] = 1;
while (q.size()) {
const int u = q.back();
q.pop_back();
for (auto [v, i] : gg[u]) {
if (visited[v]) continue;
if (x[i % M] == i / M) {
visited[v] = 1;
q.push_back(v);
}
}
}
return visited[B];
}
void answer(int a, int b) {
ANSWER_COUNT++;
if (ANSWER_COUNT > 1) {
wrong_answer(ANSWER_TWICE);
}
if (!(0 <= a && a < N)) {
wrong_answer(INVALID_A_VALUE);
}
if (!(0 <= b && b < N)) {
wrong_answer(INVALID_B_VALUE);
}
if (!(a == A && b == B)) {
wrong_answer(WRONG_ANSWER);
}
}
int main() {
assert(scanf("%d%d%d%d", &N, &M, &A, &B) == 4);
assert(N >= 0);
assert(M >= 0);
srand(6);
U.resize(M);
V.resize(M);
gg.resize(N);
for (int i = 0; i < M; i++) {
int& u = U[i];
int& v = V[i];
assert(scanf("%d%d", &u, &v) == 2);
if(rand()%2)swap(u,v);
if (!(0 <= u && u < N)) {
fprintf(stderr, "Invalid value of U[%d]: %d\n", i, u);
return 1;
}
if (!(0 <= v && v < N)) {
fprintf(stderr, "Invalid value of V[%d]: %d\n", i, v);
return 1;
}
gg[u].emplace_back(v, i);
gg[v].emplace_back(u, M + i);
}
solve(N, M, U, V);
if (ANSWER_COUNT == 0) {
wrong_answer(NO_ANSWER);
}
printf("Accepted");
}
