来自 Bajtocji 的两家电信公司不久后将在轨道上各部署 $n$ 颗卫星，为全国提供互联网服务。第一家公司的卫星编号为 $1$ 到 $n$，第二家公司的卫星编号为 $n+1$ 到 $2n$。

为了使系统正常运行，同一家公司的每对卫星之间必须建立直接通信。虽然两家公司在客户方面存在竞争，但为了应对不可预见的故障，它们决定，属于不同公司的某些卫星对之间也应建立直接通信。

现在需要为每颗卫星分配一个唯一的识别码，该识别码是由集合 $\{A, B, C\}$ 中的 $m$ 个字母组成的字符串。卫星之间的通信取决于它们的编码：编码为 $a_1a_2 \dots a_m$ 的卫星与编码为 $b_1b_2 \dots b_m$ 的卫星进行通信，当且仅当这两个编码在至少一个位置上的字母相同（即存在 $1 \le i \le m$，使得 $a_i = b_i$）。

你的任务是为卫星分配编码。

输入格式

输入的第一行包含三个整数 $n, p$ 和 $M$ ($2 \le n \le 1000, 1 \le p \le n^2$)，分别表示每家公司的卫星数量、不同公司卫星之间所需的连接数以及编码长度的限制。

接下来的 $p$ 行描述了连接情况：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \le n < b_i \le 2n$)，表示编号为 $a_i$ 和 $b_i$ 的卫星必须建立直接连接。

输出格式

你的程序应在第一行输出一个整数 $m$ ($1 \le m \le M$)，表示分配给卫星的识别码长度。

接下来的 $2n$ 行应输出编码；第 $i$ 行应包含一个由集合 $\{A, B, C\}$ 中的 $m$ 个字母组成的字符串，即分配给编号为 $i$ 的卫星的编码。

所有编码必须两两不同，且建立连接的卫星对必须符合输入的要求。

样例

输入 1

3 4 4
1 4
2 6
3 4
3 6

输出 1

3
ABA
AAC
BAA
BBB
CCB
BCC

说明 1

卫星 1 的编码为 ABA，卫星 4 的编码为 BBB；它们之间进行通信，因为它们在编码的第二个位置上都有相同的字母 B。

评分

测试集分为以下子任务。每个子任务的测试用例由一个或多个独立的测试组组成。