#include #include #include #include namespace nono { template struct EdgeBase { int from; int to; T weight; EdgeBase() {} EdgeBase(int from, int to, T weight = 1): from(from), to(to), weight(weight) {} }; using Edge = EdgeBase; template using WeightedEdge = EdgeBase; template class Graph { struct Edge_ { int to; T weight; int id; }; using iterator = std::vector::iterator; using const_iterator = std::vector::const_iterator; using subrange = std::ranges::subrange; using const_subrange = std::ranges::subrange; public: template friend Graph to_undirected_graph(int n, const std::vector>& edges); template friend Graph to_directed_graph(int n, const std::vector>& edges); subrange operator[](int i) { return std::ranges::subrange(edges_.begin() + indptr_[i], edges_.begin() + indptr_[i + 1]); } const_subrange operator[](int i) const { return std::ranges::subrange(edges_.begin() + indptr_[i], edges_.begin() + indptr_[i + 1]); } int size() const { return n_; } int edge_size() const { return m_; } bool is_directed() const { return directed_; } bool is_undirected() const { return !is_directed(); } private: Graph(int n, const std::vector>& edges, bool directed) : n_(n), m_(edges.size()), indptr_(n_ + 1), edges_(directed ? edges.size() : 2 * edges.size()), directed_(directed) { for (const auto& e: edges) { indptr_[e.from + 1]++; if (!directed_) indptr_[e.to + 1]++; } for (int i = 0; i < n_; i++) { indptr_[i + 1] += indptr_[i]; } auto index = indptr_; for (int i = 0; i < std::ssize(edges); i++) { const auto& e = edges[i]; edges_[index[e.from]++] = Edge_(e.to, e.weight, i); if (!directed_) edges_[index[e.to]++] = Edge_(e.from, e.weight, i); } } int n_; int m_; std::vector indptr_; std::vector edges_; bool directed_; }; template Graph to_undirected_graph(int n, const std::vector>& edges) { return Graph(n, edges, false); } template Graph to_directed_graph(int n, const std::vector>& edges) { return Graph(n, edges, true); } } // namespace nono #include #include #include namespace nono { template std::vector bfs(const Graph& graph, int source) { constexpr T NONE = std::numeric_limits::min(); std::vector dist(graph.size(), NONE); dist[source] = 0; std::queue que; que.push(source); while (!que.empty()) { int u = que.front(); que.pop(); for (const auto& e: graph[u]) { if (dist[e.to] == NONE) { dist[e.to] = dist[u] + e.weight; que.push(e.to); } } } return dist; } } // namespace nono namespace nono { void solve() { int n, m; int s, t, k; std::cin >> n >> m >> s >> t >> k; if (n == 1) { std::cout << "No" << '\n'; return; } if (s == t && k % 2 == 1) { std::cout << "No" << '\n'; return; } s--; t--; std::vector edges; for (int i = 0; i < m; i++) { int u, v; std::cin >> u >> v; u--; v--; edges.emplace_back(u, v); } auto graph = to_undirected_graph(n, edges); auto dist = bfs(graph, s); int count = 0; for (int i = 0; i < n; i++) { if (dist[i] >= 0) { count++; } } if (s == t && count == 1) { std::cout << "Unknown" << '\n'; return; } if (dist[t] < 0) { std::cout << "Unknown" << '\n'; } else if (dist[t] % 2 != k % 2) { std::cout << "No" << '\n'; } else if (dist[t] <= k) { std::cout << "Yes" << '\n'; } else { std::cout << "Unknown" << '\n'; } } } // namespace nono int main() { std::cin.tie(0)->sync_with_stdio(0); std::cout << std::fixed << std::setprecision(16); int t = 1; while (t--) nono::solve(); }