#include #include using namespace std; using namespace atcoder; #define rep(i,t,n) for(long long i=t;i A(N,i) #define vd(A,N,i) vector A(N,i) #define vc(A,N,i) vector A(N,i) #define vs(A,N,i) vector A(N,i) #define vb(A,N,i) vector A(N,i) #define vp(A,N,i) vector A(N,{i,i}) #define vvi(A,N,M,i) vector> A(N,vector(M,i)) #define vvd(A,N,M,i) vector> A(N,vector(M,i)) #define vvc(A,N,M,i) vector> A(N,vector(M,i)) #define vvb(A,N,M,i) vector> A(N,vector(M,i)) #define vvvi(A,N,M,L,i) vector>> A(N,vector>(M,vector(L,i))) #define ll long long #define INF ((1LL<<62)-(1LL<<31)) #define ALL(a) (a).begin(),(a).end() //((a+b+c)-max(a,max(b,c))-min(a,min(b,c))) //cout << fixed << setprecision(桁数); using VVi=vector>; using Pair=pair; using graphi=vector>; using graphp=vector>; struct Plane{ ll x; ll y; }; struct Path{ ll cost; ll to; }; template void CIN(vector &A){ rep(i,0,(ll)A.size()){ cin>>A[i]; } return; } struct ThreePlane{ ll x,y,z; ThreePlane(ll X=0,ll Y=0,ll Z=0):x(X),y(Y),z(Z){} bool operator<(const ThreePlane& other) const { return x(const ThreePlane& other) const { return x>other.x; } bool operator>=(const ThreePlane& other) const { return x>=other.x; } }; struct FourPlane{ ll dist; ll x; ll y; ll stat; }; struct Fraction{ ll p,q,r; Fraction(ll P = 0, ll Q = 1,ll R = 1): p(P), q(Q),r(R){} bool operator<(const Fraction &other)const{ if(p*other.q != other.p*q){ return p*other.q < other.p*q; }else{ return r>other.r; } } }; struct Matrix{//正方のみ vector> mat; Matrix(ll size):mat(vector>(size,vector(size,0))){} void showerr(){ rep2(i,mat){ rep2(j,i)cerr< struct Zaatu{ bool sorted; vector za; Zaatu():sorted(false){} void add(T x){ za.push_back(x); sorted=false; } void build(){ sort(std::begin(za),std::end(za)); sorted=true; za.erase(unique(std::begin(za),std::end(za)),std::end(za)); } ll size(){ if(!sorted)build(); return (ll)za.size(); } const T &operator[](int i){ if(!sorted)build(); return za[i]; } ll get(const T &x){//x以上の最小値のindex if(!sorted)build(); return lower_bound(std::begin(za),std::end(za),x)-std::begin(za); } vector get(vector mo){ if(!sorted)build(); vector result; transform(std::begin(mo),std::end(mo),back_inserter(result),[&](const T &x){ return lower_bound(std::begin(za),std::end(za),x)-std::begin(za); }); return result; } typename vector::iterator begin(){ if(!sorted)build(); return std::begin(za); } typename vector::iterator end(){ if(!sorted)build(); return std::end(za); } }; ll POW(ll a,ll b,ll mod){ ll c=1; a%=mod; while(b!=0){ if(b%2){ c*=a; c%=mod; } a*=a; a%=mod; b/=2; } return c; } ll GCD(ll a,ll b){ if(b==0)return a; return GCD(b,a%b); } pair extGCD(long long a, long long b) {// ax+by=1 solver if (b == 0) return make_pair(1, 0); long long x,y; tie(y,x)=extGCD(b,a%b); y-=a/b*x; return make_pair(x,y); } ll SQRT(ll a){ ll low,high,mid; low=0; high=1LL<<31; while(high-low!=1){ mid=(low+high)/2; if(mid*mid<=a){ low=mid; }else{ high=mid; } } return low; } string strmin(string x,string y){ ll minlength=min((int)x.size(),(int)y.size()); rep(i,0,minlength){ if(x[i]>y[i])return y; if(x[i](int)y.size())return y; return x; } ll LCS(string x,string y){ ll xsize=(ll)x.size(); ll ysize=(ll)y.size(); vvi(dp,xsize+1,ysize+1,0); rep(i,1,xsize+1){ rep(j,1,ysize+1){ if(x[i-1]==y[j-1])dp[i][j]=max(max(dp[i-1][j-1]+1,dp[i][j-1]),dp[i-1][j]); else dp[i][j]=max(dp[i][j-1],dp[i-1][j]); } } return dp[xsize][ysize]; } ll Factorial(ll n,ll mod){ ll a=1; if(n>=mod)return 0; rep(i,1,n+1){ a*=i; a%=mod; } return a; } ll Combination(ll n,ll k,ll mod){ if(n> RLE(string x,char s=' ',long long a=0,vector> res={}){ for(auto i:x){ if(s==i){ a++; }else{ if(s!=' ')res.push_back({s,a}); s=i,a=1; } } res.push_back({s,a}); return res; } vector cu1d(vector A){ ll cu1=A.size(); vector res(cu1+1,0); rep(i,0,cu1)res[i+1]=A[i]; rep(i,1,cu1+1)res[i]+=res[i-1]; return res; } vector> cu2d(vector> A){ ll cu1=A.size(),cu2=A[0].size(); vector> res(cu1+1,vector(cu2+1,0)); rep(i,0,cu1)rep(j,0,cu2)res[i+1][j+1]=A[i][j]; rep(i,1,cu1+1)rep(j,0,cu2+1)res[i][j]+=res[i-1][j]; rep(j,0,cu1+1)rep(i,1,cu2+1)res[j][i]+=res[j][i-1]; return res; } ll LIS(vector A){ ll a=(ll)A.size(); vector result(a,INF); ll answer=0; rep(i,0,a){ ll ok=-1; ll ng=a; while(ng-ok!=1){ ll mid=(ok+ng)/2; if(A[i]<=result[mid])ng=mid; else ok=mid; } result[ok+1]=A[i]; answer=max(answer,ok+2); } return answer; } vector zaatu(vector A){ vector B=A; Sort(B); B.erase(unique(ALL(B)),end(B)); vector res; transform(ALL(A),back_inserter(res),[&](const ll &x){ return lower_bound(ALL(B),x)-begin(B); }); return res; } vector trim(vector A){ bool frag=0; char s='#'; ll h=(ll)A.size(); ll w=(ll)A[0].size(); ll a=-1,b=h,c=-1,d=w; for(ll i=0;i=0;i--){ for(ll j=0;j=0;i--){ for(ll j=0;j B(b-a-1,""); for(ll i=a+1;i> Warshall(vector> A){ ll a=A.size(); rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]); return A; } //Warshall rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]); long long a,b,c,d,e,f,g,h,ans=0; string w,x="",y="",z=""; char s,t,u; bool frag=false,frag1=false,frag2=false; vector X={1,0,-1,0},Y={0,1,0,-1}; bool dp[5050][8192][4]={}; // vvvi(dp,5050,8192,2,0); int main(){ cin>>a>>b>>c>>d>>e; c--,d--; graphi A(a); rep(i,0,b){ cin>>f>>g; f--,g--; A[f].push_back(g); A[g].push_back(f); } vi(B,a,INF); B[c]=0; queue Q; Q.push(c); while(!Q.empty()){ ll q=Q.front(); Q.pop(); rep2(i,A[q]){ if(B[i]!=INF)continue; B[i]=B[q]+1; Q.push(i); } } ll k=e; if(B[d]==INF){ rep(i,0,a){ if(B[i]%2!=e%2){ cout<<"Unknown"<=B[d]){ cout<<"Yes"<