在字节国（Byteland），有 $N$ 座城市通过双向道路连接。字节国国王决定将政治体制改为联邦制共和国，并设立恰好 $K$ 个州（每个州由若干城市组成）。

国王不希望发生革命，因此他咨询了政治科学家。他们建议，改革政治体制最简单的方法是将每条道路改为单向道路，并将城市划分为若干个州，遵循以下简单规则：对于任意两座城市 $A$ 和 $B$，它们属于同一个州，当且仅当存在从 $A$ 到 $B$ 的路径，且同时也存在从 $B$ 到 $A$ 的路径。你是王国中最优秀的程序员，所以你应该调查是否可以在没有痛苦和恐惧的情况下进行改革。

输入格式

输入的第一行包含三个整数：$N$（城市数量）、$M$（道路数量）和 $K$（要求的州数量）。数据范围为 $1 \le N \le 16$，$0 \le M \le 10^5$，$1 \le K \le N$。接下来的 $M$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示第 $i$ 条道路连接的城市编号（$1 \le u_i, v_i \le N$）。

输出格式

如果改革无法实现，输出 "NO"。否则，在第一行输出 "YES"，并在接下来的 $M$ 行中输出改革方案。这 $M$ 行中的每一行对应输入中的一条边。输出边的顺序必须与输入中的顺序相同。第 $i$ 行应包含两个整数 $u_i$ 和 $v_i$，中间用空格隔开。顺序很重要：如果你输出 $u_i$ 和 $v_i$，则第 $i$ 条道路的方向是从 $u_i$ 到 $v_i$；如果你输出 $v_i$ 和 $u_i$，则道路的方向是从 $v_i$ 到 $u_i$。

样例

样例输入 1

5 6 3
1 2
2 3
3 1
1 4
2 5
4 5

样例输出 1

YES
1 2
2 3
3 1
4 1
5 2
5 4

样例输入 2

5 6 4
1 2
2 3
3 1
1 4
2 5
4 5

样例输出 2

NO

样例输入 3

16 0 16

样例输出 3

YES