#pragma region template #include using namespace std; //other // #include // #include // using namespace __gnu_pbds; #include using namespace atcoder; // #include "atcoder/modint.hpp" using mint = atcoder::modint998244353; using zint = atcoder::modint1000000007; // using mint=modint; #define int long long #define pb push_back #define eb emplace_back #define ep emplace #define len(a) (int)a.size() #define BIT(a,b) ((a)>>(b)&1) // #define endl "\n" // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //using using ll=long long; using i32=signed; using i64=long long; using i128=__int128_t; using ld=long double; using ull=unsigned long long; using uint=unsigned; using pcc=pair; using pii=pair; using pll=pair; using pdd=pair; using vi=vector; using vl=vector; using vvi=vector; using vvl=vector; using vvvi=vector; using vvvl=vector; templateusing V=vector; templateusing VV=vector>; templateusing VVV=vector>; templateusing VVVV=vector>; templateusing VVVVV=vector>; templateusing pqmin=priority_queue,greater>; templateusing pqmax=priority_queue; // templateusing pbds=tree, rb_tree_tag, tree_order_statistics_node_update>; #define chmax(a,b) (a)=max((a),(b)) #define chmin(a,b) (a)=min((a),(b)) const ll LINF=0x1fffffffffffffff; const int INF=0x3fffffff; const int MOD=998244353; const int MOD2=1000000007; const ld PI=3.1415926535897932384626433832795028841971; const ld DINF=numeric_limits::infinity(); const ld EPS=1e-9; const ll di[]={0,1,0,-1,1,-1,1,-1}; const ll dj[]={1,0,-1,0,1,1,-1,-1}; template constexpr auto min(T a,T b,T c){ return min(a,min(b,c)); } template constexpr auto min(T... a){ return min(initializer_list>{a...}); } template constexpr auto max(T a,T b,T c){ return max(a,max(b,c)); } template constexpr auto max(T... a){ return max(initializer_list>{a...}); } #define overload4(_1,_2,_3,_4,name,...) name #define overload3(_1,_2,_3,name,...) name #define rep1(n) for(ll i=0;i(a);) #define rrep4(i,a,b,c)for(ll=(a)+((b)-(a)-1)/(c)*(c);i>=(a);i-=c) #define rrep(...) overload4(__VA_ARGS__,rrpe4,rrep3,rrep2,rrep1)(__VA_ARGS__) #define isum(...) accumulate(all(__VA_ARGS__),0LL) #define dsum(...) accumulate(all(__VA_ARGS__),0.0L) #define Msum(...) accumulate(all(__VA_ARGS__),0_M) #define elif else if #define INT(...) int __VA_ARGS__;input(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;input(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__;input(__VA_ARGS__) #define STR(...) string __VA_ARGS__;input(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;input(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;input(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;input(__VA_ARGS__) //io //in void scan(){} void scan(signed &a){cin>>a;} void scan(unsigned &a){cin>>a;} void scan(long& a){cin>>a;} void scan(long long& a){cin>>a;} void scan(unsigned long long&a){cin>>a;} void scan(char& a){cin>>a;} void scan(float& a){cin>>a;} void scan(double& a){cin>>a;} void scan(long double& a){cin>>a;} void scan(vector& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } } void scan(char a[]){ scanf("%s", a); } void scan(string& a){cin>>a;} template void scan(vector&); template void scan(array&); template void scan(pair&); template void scan(T(&)[size]); template void scan(vector& a){ for(auto&& i : a) scan(i); } template void scan(deque& a){ for(auto&& i : a) scan(i); } template void scan(array& a){ for(auto&& i : a) scan(i); } template void scan(pair& p){ scan(p.first); scan(p.second); } template void scan(T (&a)[size]){ for(auto&& i : a) scan(i); } template void scan(T& a){ cin >> a; } void input(){} template void input(Head& head,Tail&... tail){scan(head);input(tail...);} //out void puts(){ putchar(' '); } void puts(bool a){ printf("%d", a); } void puts(signed a){ printf("%d", a); } void puts(unsigned a){ printf("%u", a); } void puts(long a){ printf("%ld", a); } void puts(long long a){ printf("%lld", a); } void puts(unsigned long long a){ printf("%llu", a); } void puts(char a){ printf("%c", a); } void puts(char a[]){ printf("%s", a); } // void puts(const char a[]){ printf("%s", a); } void puts(float a){ printf("%.15f", a); } void puts(double a){ printf("%.15f", a); } void puts(long double a){ printf("%.15Lf", a); } void puts(const string& a){ for(auto&& i : a) puts(i); } template void puts(const complex& a){ if(a.real() >= 0) puts('+'); puts(a.real()); if(a.imag() >= 0) puts('+'); puts(a.imag()); puts('i'); } template void puts(const vector&); template void puts(const array&); template void puts(const pair& p); template void puts(const T (&)[size]); template void puts(const vector& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template void puts(const deque& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template void puts(const set& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template void puts(const multiset& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template void puts(const array& a){ puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template void puts(const pair& p){ putchar('(');puts(p.first); putchar(' '); puts(p.second); putchar(')');} template void puts(const T (&a)[size]){ puts(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); puts(*i); } } template void puts(const T& a){ cout << a; } int print(){ putchar('\n'); return 0; } template int print(const T& t){ puts(t); putchar('\n'); return 0; } template int print(const Head& head, const Tail&... tail){ puts(head); putchar(' '); print(tail...); return 0; } #pragma endregion #pragma region commonly used int digitsum(string s){ int res=0; rep(i,(int)s.size()){ res+=s[i]-'0'; } return res; } //乱数系 random_device rnd; mt19937 mt(rnd()); const long long MT_MAX=LINF; uniform_int_distribution rd(0,MT_MAX); double randd(){ return 1.0*rd(mt)/MT_MAX; } long long randint(long long a,long long b){ // [a,b]の乱数を生成 return a+rd(mt)%(b-a+1); } std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } __int128 parse(string &s) { __int128 ret = 0; for (int i = 0; i < (int)s.length(); i++) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0'; return ret; } // #include // using lint=boost::multiprecision::cpp_int; #pragma endregion vector dijkstra(vector>> &g,int start){ priority_queue,vector>,greater>> q; vector kakutei(g.size(),false); vector dis(g.size(),(int)1e15); q.push(make_pair(0,start)); dis[start]=0; while(!q.empty()){ pair p=q.top();q.pop(); int pos=p.second,cost=p.first; if(kakutei[pos])continue; kakutei[pos]=true; for(auto nex:g[pos]){ int npos=nex.first,ncos=nex.second; if(dis[npos]>cost+ncos){ dis[npos]=cost+ncos; q.push(make_pair(dis[npos],npos)); } } } return dis; } signed main(){ INT(n,m); INT(s,t,k);s--;t--; VV> g(n); rep(i,m){ INT(a,b);a--;b--; g[a].pb({b,1}); g[b].pb({a,1}); } auto d=dijkstra(g,s); // print(d); cout<<"Unknown"<