题目描述

题目译自 XXXI Olimpiada Informatyczna – I etap Satelity

Bajtocja 的两家电信公司将在不久的将来各自发射 $n$ 颗卫星，为全国提供互联网服务。第一家公司的卫星编号为 $1$ 到 $n$，而第二家公司的卫星编号为 $n+1$ 到 $2n$。

为了保证系统的正常运行，每一对属于同一家公司的卫星必须建立直接的通信连接。虽然两家公司会争夺客户，但为了应对意外的故障，他们决定让一些属于不同公司的卫星也建立直接的通信连接。对于剩下的来自不同公司的卫星对，它们之间不应该存在直接的通信连接。

现在需要给每个卫星分配一个唯一的识别码，它是由 $m$ 个字母 $\{\texttt{A}, \texttt{B}, \texttt{C}\}$ 组成的字符串。哪些卫星会相互通信，取决于它们的识别码：如果卫星的识别码是 $a_{1} a_{2} \ldots a_{m}$，而另一个卫星的识别码是 $b_{1} b_{2} \ldots b_{m}$，那么它们会相互通信当且仅当这两个识别码在至少一个位置上有相同的字母（即存在 $1 \leq i \leq m$，使得 $a_{i}=b_{i}$）。

你的任务是给卫星分配识别码。

输入格式

第一行包含三个整数 $n,p,M\ (2 \leq n \leq 1000,1 \leq p \leq n^{2})$，表示每家公司的卫星数量，要求建立的不同公司卫星之间的通信连接数，以及识别码的长度的限制。

接下来的 $p$ 行描述了通信连接：第 $i$ 行包含两个整数 $a_{i},b_{i}\ (1 \leq a_{i} \leq n<b_{i} \leq 2 n)$，表示编号为 $a_{i}$ 和 $b_{i}$ 的卫星必须建立直接的通信连接。对于输入中不存在的来自不同公司的卫星对，它们之间不应该存在直接的通信连接。

输出格式

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

接下来的 $2 n$ 行输出识别码；第 $i$ 行应该包含一个由 $m$ 个字母 $\{\texttt{A}, \texttt{B}, \texttt{C}\}$ 组成的字符串，表示编号为 $i$ 的卫星的识别码。

所有的识别码必须两两不同，而且要求建立通信连接的卫星对应的识别码必须满足输入中的条件。

3 4 4
1 4
2 6
3 4
3 6

3
ABA
AAC
BAA
BBB
CCB
BCC

编号为 $1$ 的卫星的识别码是 $\texttt{ABA}$，而编号为 $4$ 的卫星的识别码是 $\texttt{BBB}$；它们之间会建立通信连接，因为它们的识别码在第二个位置上都是 $\texttt{B}$。

样例 2

见附加文件下 [sat1ocen.in](file:sat1ocen.in) 和 [sat1ocen.out](file:sat1ocen.out)。

该样例满足 $n=p=100, M=10200$，要求建立通信连接的卫星是 $i$ 和 $n+i\ (1\leq i \leq n)$；

样例 3

见附加文件下 [sat2ocen.in](file:sat2ocen.in) 和 [sat2ocen.out](file:sat2ocen.out)。

该样例满足 $n=p=100, M=10200$，要求建立通信连接的卫星是 $i$ 和 $n+i\ (1\leq i \leq n)$；

样例 4

见附加文件下 [sat3ocen.in](file:sat3ocen.in) 和 [sat3ocen.out](file:sat3ocen.out)。

该样例满足 $n=2, p=1, M=4$，要求建立通信连接的卫星是 $1$ 和 $4$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分数
$1$	$n \leq 100, M=n^{2}+2 n$	$7$
$2$	$M=3 n$	$11$
$3$	$M=n+2\left\lceil\log _{2} n\right\rceil$	$23$
$4$	$M=n+2$	$41$
$5$	$M=n+1$	$18$