問題文

グラフの頂点 $s, t$ に対して、「 $s$ から隣接頂点への移動を $k$ 回繰り返して $t$ へ移動する経路」のことを $s$ から $t$ への長さ $k$ の歩道と呼びます。

まず始めに、eoeo はこのような問題を考えました。

頂点集合 $V$ と辺集合 $E$ からなる単純無向二部グラフ $G$ 、その頂点 $s, t$、正整数 $k$ が与えられます。
グラフ $G$ に $s$ から $t$ への長さ $k$ の歩道が存在するか判定してください。

しかしこのままではシンプルすぎます。 nu50218 は上の問題に一捻り加えて、辺集合 $E$ の代わりに $E$ から $0$ 本以上の辺を削除した $F$ を入力として与えることにしました。 改変された以下の問題を解いてください。

単純無向二部グラフ $G$ の頂点数 $N$ 、辺集合の部分集合 $F \subseteq E$、頂点 $s, t$、正整数 $k$ が与えられます。

与えられた情報のみから、グラフ $G$ に $s$ から $t$ への長さ $k$ の歩道が

• 存在すると確定するとき Yes 、
• 存在しないと確定するとき No 、
• 上記のいずれでもないとき Unknown

を出力してください。

入力

入力は以下の形式で標準入力から与えられます。

グラフの $N$ 個の頂点はそれぞれ $1, 2, \dots, N$ と番号付けられています。

$M = |F|$ であり、 $A_i, B_i$ は $F$ の $i$ 本目の辺の端点です。

$N$ $M$
$s$ $t$ $k$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

出力

標準出力へ一行で出力し、最後に改行してください。

制約

入力は以下の制約を満たします。

• 入力はすべて整数
• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq s, t \leq N$
• $1 \leq k \leq 10^9$
• $1 \leq A_i < B_i \leq N$
• $i \neq j$ ならば $(A_i, B_i) \neq (A_j, B_j)$
• グラフ $(V, F)$ は二部グラフである

サンプル

4 3
1 4 5
1 2
2 3
3 4

Yes

4 3
1 3 3
1 2
2 3
3 4

No

4 3
1 4 1
1 2
2 3
3 4

Unknown