#include //#include using namespace std; //using namespace atcoder; using ll = long long; //using mint = modint998244353; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); /* Kが奇数 ->s,tを結べば1,3,5,....ステップ目に到達できるのでOK Kが偶数 tがs以外の頂点と隣接しているとき、tに隣接する頂点とsを結べば2,4,...ステップ目に到達できるのでOK sがt以外の頂点と隣接しているとき、sに隣接する頂点とtを結べば2,4,...ステップ目に到達できるのでOK それ以外のとき、 (1)s, tが孤立しているときs, tを結ばないと到達できない。しかし、この場合、1,3,5,...ステップ目でしか到達できないのでNG (2)s-tのグループが孤立している時、グラフに存在する奇数長の閉路の最小値をxとする。tからその閉路に辺を伸ばすと、x+3, x+5,...で到着できる。 これは、グラフの頂点を倍加させて、奇数、偶数の状態を持たせ、奇数τ行の最短距離を求めれば良い。 */ ll N, M, K, s, t; cin >> N >> M >> K >> s >> t; s--; t--; vector> E(N); vector con(N, vector(N)); while(M--){ ll u, v; cin >> u >> v; u--; v--; E[u].push_back(v); E[v].push_back(u); } auto yes=[]()->void{ cout << "Yes" << endl; exit(0); }; if (K % 2 == 1) yes(); if (E[s].size() >= 1 && E[s][0] != t) yes(); if (E[t].size() >= 1 && E[t][0] != s) yes(); if (E[s].size() == 0 && E[t].size() == 0){ cout << "No" << endl; return 0; } assert(E[s][0] == t && E[t][0] == s); auto min_cycle=[&](ll x)->ll{ vector dist(N, vector(2, -1)); queue> que; dist[x][0] = 0; que.push({x, 0}); while(!que.empty()){ auto [from, sign] = que.front(); que.pop(); for (auto to : E[from]){ if (dist[to][(sign+1)%2] == -1){ dist[to][(sign+1)%2] = dist[from][sign]+1; que.push({to, (sign+1)%2}); } } } return (dist[x][1] == -1 ? (ll)9e18 : dist[x][1]); }; ll mi=9e18; for (int i=0; i