Problem Statement

There is an undirected complete graph^† with vertices $1,2,\dots,N$.
Remove exactly $M$ edges from this graph to create a new undirected graph $G$.
In the remaining graph $G$, you want the shortest distance (the number of edges traversed) from vertex $1$ to vertex $N$ to be exactly $K$^‡.

If there is a way to remove edges that satisfies this condition, output Yes and $1$ such set of edges to remove.
If there is no such way, output No.

^† An "undirected complete graph" is an undirected graph without self-loops or multiple edges in which there is exactly $1$ edge between any $2$ distinct vertices.
^‡ If vertex $N$ cannot be reached from vertex $1$, the condition is considered not satisfied.

Constraints

• $2 \leq N \leq 100$
• $0 \leq M \leq \dfrac{N(N-1)}{2}$
• $1 \leq K \leq N-1$
• All input values are integers.

Input

The input is given from standard input in the following format.

$N\ M\ K$

Output

If there is no way to remove edges that satisfies the condition, output

No

.

If there is such a way, output in the format

Yes
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$

.
Here, $(u_i,v_i)$ represents an edge to remove.
All edges must be distinct, and for each $i$, $1 \leq u_i,v_i \leq N$ and $u_i \neq v_i$ must hold.

If there are multiple valid outputs, any of them will be accepted.

Sample

5 5 3

Yes
1 3
1 4
1 5
2 5
4 5

4 2 3

No