// #pragma GCC optimize("O3,unroll-loops") #include // #include using namespace std; #if __cplusplus >= 202002L using namespace numbers; #endif template struct disjoint_set{ int n, _group_count; vector p; vector> group; disjoint_set(){ } disjoint_set(int n): n(n), _group_count(n), p(n, -1), group(n){ assert(n >= 0); for(auto i = 0; i < n; ++ i) group[i] = {i}; } int make_set(){ p.push_back(-1); group.push_back(list{p}); ++ _group_count; return n ++; } int root(int u){ return p[u] < 0 ? u : p[u] = root(p[u]); } bool share(int a, int b){ return root(a) == root(b); } int size(int u){ return -p[root(u)]; } bool merge(int u, int v){ u = root(u), v = root(v); if(u == v) return false; -- _group_count; if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v); p[u] += p[v], p[v] = u; group[u].splice(group[u].end(), group[v]); return true; } bool merge(int u, int v, auto act){ u = root(u), v = root(v); if(u == v) return false; -- _group_count; bool swapped = false; if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true; p[u] += p[v], p[v] = u; group[u].splice(group[u].end(), group[v]); act(u, v, swapped); return true; } int group_count() const{ return _group_count; } const list &group_of(int u){ return group[root(u)]; } vector> group_up(){ vector> g(n); for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i); g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end()); return g; } void clear(){ _group_count = n; fill(p.begin(), p.end(), -1); for(auto i = 0; i < n; ++ i) group[i] = {i}; } friend ostream &operator<<(ostream &out, disjoint_set dsu){ auto gs = dsu.group_up(); out << "{"; if(!gs.empty()) for(auto i = 0; i < (int)gs.size(); ++ i){ out << "{"; for(auto j = 0; j < (int)gs[i].size(); ++ j){ out << gs[i][j]; if(j + 1 < (int)gs[i].size()) out << ", "; } out << "}"; if(i + 1 < (int)gs.size()) out << ", "; } return out << "}"; } }; template struct graph{ using Weight_t = T; struct Edge_t{ int from, to; T cost; }; int n; vector edge; vector> adj; function ignore; graph(int n = 1): n(n), adj(n){ assert(n >= 1); } graph(const vector> &adj, bool undirected = true): n((int)adj.size()), adj(n){ assert(n >= 1); if(undirected){ for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v); } else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v); } graph(const vector>> &adj, bool undirected = true): n((int)adj.size()), adj(n){ assert(n >= 1); if(undirected){ for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w); } else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w); } graph(int n, vector> &edge, bool undirected = true): n(n), adj(n){ assert(n >= 1); for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v); } graph(int n, vector> &edge, bool undirected = true): n(n), adj(n){ assert(n >= 1); for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w); } int operator()(int u, int id) const{ #ifdef LOCAL assert(0 <= id && id < (int)edge.size()); assert(edge[id].from == u || edge[id].to == u); #endif return u ^ edge[id].from ^ edge[id].to; } int link(int u, int v, T w = {}){ // insert an undirected edge int id = (int)edge.size(); adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w}); return id; } int orient(int u, int v, T w = {}){ // insert a directed edge int id = (int)edge.size(); adj[u].push_back(id), edge.push_back({u, v, w}); return id; } void clear(){ for(auto [u, v, w]: edge){ adj[u].clear(); adj[v].clear(); } edge.clear(); ignore = {}; } graph transposed() const{ // the transpose of the directed graph graph res(n); for(auto &e: edge) res.orient(e.to, e.from, e.cost); res.ignore = ignore; return res; } int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule) return (int)adj[u].size(); } // The adjacency list is sorted for each vertex. vector> get_adjacency_list() const{ vector> res(n); for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){ if(ignore && ignore(id)) continue; res[(*this)(u, id)].push_back(u); } return res; } void set_ignoration_rule(const function &f){ ignore = f; } void reset_ignoration_rule(){ ignore = nullptr; } friend ostream &operator<<(ostream &out, const graph &g){ for(auto id = 0; id < (int)g.edge.size(); ++ id){ if(g.ignore && g.ignore(id)) continue; auto &e = g.edge[id]; out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n"; } return out; } }; // Requires graph template struct bfs_forest{ int n; T base_dist; vector dist; vector pv; vector pe; vector order; vector pos; vector size; vector root_of; vector root; vector depth; vector was; bfs_forest(T base_dist = 0): base_dist(base_dist){ } void init(int n){ this->n = n; pv.assign(n, -1); pe.assign(n, -1); order.clear(); pos.assign(n, -1); size.assign(n, -1); root_of.assign(n, -1); root.clear(); depth.assign(n, -1); dist.assign(n, base_dist); was.assign(n, -2); attempt = -1; } int attempt; vector q; // O(# of nodes reachable from src) template> void _bfs(const graph &g, const vector &src, F UT = plus<>()){ q = src; for(auto u: src){ assert(was[u] != attempt); was[u] = attempt; depth[u] = 0; dist[u] = base_dist; root_of[u] = u; root.push_back(u); pv[u] = -1; pe[u] = -1; size[u] = 1; } int init_size = (int)order.size(); for(auto it = 0; it < (int)q.size(); ++ it){ int u = q[it]; pos[u] = (int)order.size(); order.push_back(u); for(auto id: g.adj[u]){ if(g.ignore && g.ignore(id)) continue; int v = g(u, id); if(was[v] == attempt) continue; was[v] = attempt; depth[v] = depth[u] + 1; dist[v] = UT(g.edge[id].cost, dist[u]); pv[v] = u; pe[v] = id; root_of[v] = root_of[u]; q.push_back(v); } } for(auto i = (int)order.size() - 1; i >= init_size; -- i){ int u = order[i]; for(auto id: g.adj[u]){ if(g.ignore && g.ignore(id)) continue; if(~pv[u]) size[pv[u]] += size[u]; } } q.clear(); } // O(# of nodes reachable from src) template> void bfs(const graph &g, const vector &src, F UT = plus<>()){ assert(g.n <= n); root.clear(), order.clear(); for(auto u: src) assert(0 <= u && u < g.n); ++ attempt; _bfs(g, src, UT); } // O(n + m) template> void bfs_all(const graph &g, F UT = plus<>()){ assert(g.n <= n); root.clear(), order.clear(); ++ attempt; for(auto u = 0; u < g.n; ++ u) if(was[u] != attempt) _bfs(g, {u}, UT); } // Check if u is visited during the last bfs-like call. bool visited(int u) const{ assert(0 <= u && u < n); return was[u] == attempt; } vector get_path(int u, int v) const{ assert(visited(u) && visited(v) && root_of[u] == root_of[v]); vector left, right; while(u != v){ if(depth[u] >= depth[v]){ left.push_back(u); u = pv[u]; } else{ right.push_back(v); v = pv[v]; } } left.push_back(u); left.insert(left.end(), right.rbegin(), right.rend()); return left; } }; int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int n, m, from, to, len; cin >> n >> m >> from >> to >> len, -- from, -- to; disjoint_set dsu(n << 1); graph g(n); for(auto i = 0; i < m; ++ i){ int u, v; cin >> u >> v, -- u, -- v; dsu.merge(u << 1, v << 1 | 1); dsu.merge(u << 1 | 1, v << 1); g.link(u, v); } if(n == 2){ dsu.merge(0, 3); dsu.merge(1, 2); g.link(0, 1); } bfs_forest bf; bf.init(n); bf.bfs(g, {from}); if(dsu.share(from << 1, to << 1)){ if(len & 1){ cout << "No\n"; return 0; } bf.depth[to] == len || bf.depth[to] < len && bf.size[from] >= 2 ? cout << "Yes\n" : cout << "Unknown\n"; } else if(dsu.share(from << 1, to << 1 | 1)){ if(~len & 1){ cout << "No\n"; return 0; } bf.depth[to] == len || bf.depth[to] < len && bf.size[from] >= 2 ? cout << "Yes\n" : cout << "Unknown\n"; } else{ cout << "Unknown\n"; } return 0; } /* */