Biscotti 王国的网络服务器遭到了计算机病毒的攻击！管理员 Yukikaze 正试图使用专门的杀毒程序来清除病毒。

Biscotti 王国的网络由若干节点和节点间的双向链路组成。Yukikaze 知道，在每一秒结束时，病毒会将它的克隆体从一个节点传播到该节点的所有邻居，然后从原节点消失。节点的邻居是指与该节点直接相连的节点。

Yukikaze 需要为程序设计一个策略，程序将按照该策略来发现并清除病毒。一个策略由一系列（有限数量的）步骤组成。在每一步中，杀毒程序将清除网络中的若干节点。在每一秒开始时，程序将执行一个步骤。步骤按顺序执行（从第一步到最后一步）。当指定策略中的每一步都至少执行过一次后，程序停止。如果程序停止后病毒不再存在于网络中，则该策略被视为有效。

不幸的是，杀毒程序的能力受到参数 $k$ 的限制，该参数表示程序每一步最多能影响的节点数量。在杀毒程序启动之前，网络中的每个节点都已被病毒感染。请设计一个策略来清除网络中所有节点上的病毒，或者声明这是不可能的。

输入格式

第一行包含三个整数 $n$ ($2 \le n \le 16$)，$m$ ($1 \le m \le \frac{1}{2}n(n - 1)$)，$k$ ($1 \le k \le n$)，分别表示网络中的节点数、网络中不同的链路数以及杀毒程序的参数。

接下来的 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示节点 $u$ 和 $v$ 之间的一条双向链路。

保证网络中没有孤立节点（即没有与其他任何节点相连的节点），且任意两个节点之间最多只有一条链路。

输出格式

如果无论采取何种策略都无法从网络中清除病毒，则输出一行 $-1$。

否则，按以下格式输出策略：

第一行包含一个整数 $L$ ($1 \le L \le 100$)，表示步骤的数量。

接下来的 $L$ 行，每行应包含一个非空字符串，由小写字母组成，长度小于或等于 $k$，表示每一步中要清除的节点。如果第 $i$ 个小写字母出现在输出的第 $(j + 1)$ 行中，则表示第 $i$ 个节点将在第 $j$ 步被清除。

保证对于每个输入测试用例，如果存在有效策略，则一定存在一个步骤数小于或等于 $100$ 的有效策略。

任何满足约束 $1 \le L \le 100$ 的有效策略均可接受。

样例

样例输入 1

5 4 2
1 2
2 3
3 4
2 5

样例输出 1

2
bd
bd

样例输入 2

2 1 1
1 2

样例输出 2

2
b
b

样例输入 3

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

样例输出 3

4
ce
be
de
ac

说明

尝试考虑在 $4 \times 3$ 网格图上的策略。