問題文

頂点に $1$ から $N$ までの番号が付いた、$N$ 頂点 $M$ 辺の単純有向グラフが与えられます。$i$ 番目の辺は頂点 $u_i$ から頂点 $v_i$ へ向かう有向辺です。

各頂点には $0$ 以上 $2^{K} - 1$ 以下の整数を書き込むことができるようになっており、はじめ、すべての頂点には $0$ が書き込まれています。

駒が $1$ つ頂点 $1$ においてあります。また、変数 $T$ があり、はじめ $T = 0$ です。

あなたは以下の操作を好きなだけ繰り返すことが出来ます。

• 今駒が置かれている頂点を頂点 $i$ とする。頂点 $i$ から頂点 $j$ に向かう辺が存在するような頂点 $j$ を選び、駒を頂点 $j$ に移動させる。そして、$T$ に $1$ を足した後、頂点 $j$ に書き込まれている値を $x$ として、$x$ を $x\ \text{OR}\ (T \bmod 2^{K})$ に書き換える。ここで、$A\ \text{OR}\ B$ は $A$ と $B$ のビットごとの論理和を表す。

あなたの目的は全ての頂点について、書き込まれている値を $2^K-1$ にすることです。これが可能かどうかを判定してください。

制約

• $1 \le N \le 5 \times 10^5$
• $0 \le M \le \min \left( N(N-1) ,5 \times 10^5 \right)$
• $1 \le K \le 51$
• $1\le u_i , v_i \le N$
• $u_i \ne v_i$
• $i \ne j \Rightarrow (u_i,v_i) \ne (u_j,v_j)$
• 入力は全て整数

入力

$N$ $M$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

出力

可能ならYes、そうでないならNoを1行で出力してください。

サンプル

3 3 2
1 2
2 3
3 1

Yes

3 3 2
1 2
2 3
1 3

No