Problem Statement

You are given a simple directed graph with $N$ vertices and $M$ edges, whose vertices are numbered from $1$ to $N$. The $i$-th edge is a directed edge from vertex $u_i$ to vertex $v_i$.

Each vertex can hold an integer between $0$ and $2^{K} - 1$, inclusive, and initially $0$ is written on every vertex.

There is $1$ piece placed on vertex $1$. There is also a variable $T$, initially $T = 0$.

You may repeat the following operation as many times as you like.

• Let vertex $i$ be the vertex where the piece is currently placed. Choose a vertex $j$ such that there is an edge from vertex $i$ to vertex $j$, and move the piece to vertex $j$. Then, after adding $1$ to $T$, let $x$ be the value written on vertex $j$, and rewrite $x$ to $x\ \text{OR}\ (T \bmod 2^{K})$. Here, $A\ \text{OR}\ B$ denotes the bitwise OR of $A$ and $B$.

Your goal is to make the value written on every vertex equal to $2^K-1$. Determine whether this is possible.

Constraints

• $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)$
• All input values are integers.

Input

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

Output

Print Yes if it is possible, and No otherwise, on a single line.

Sample

3 3 2
1 2
2 3
3 1

Yes

3 3 2
1 2
2 3
1 3

No