[POI 2023/2024 R1] Satelity

题目背景

译自 XXXI Olimpiada Informatyczna - I etap Satelity。

题目描述

有 $2n$ 个卫星，$1\sim n$ 属于 A 公司，$n+1\sim 2n$ 属于 B 公司。

两个卫星应当能够通信当且仅当它们属于同一个公司或者有额外要求。

你需要给每个卫星分配一个等长的独一无二的识别码，识别码应当只包含字母 ABC，两个卫星实际能够通信当且仅当识别码有至少一位相同。要求你的识别码方案满足要求。输出你的方案。

输入格式

第一行三个正整数 $n,p,M$，其中 $M$ 意为你的识别码长度不得超过 $M$。

接下来 $p$ 行，每行两个正整数，表示这两个卫星有额外要求应当能够通信。

输出格式

第一行一个正整数 $m(1\leq m\leq M)$，表示你的方案的识别码长度。

接下来 $2n$ 行，每行一个长度为 $m$ 的只含 ABC 的字符串，识别码。

样例 #1

样例输入 #1

3 4 4
1 4
2 6
3 4
3 6

样例输出 #1

3
ABA
AAC
BAA
BBB
CCB
BCC

样例 #2

样例输入 #2

见附件

样例输出 #2

见附件

样例 #3

样例输入 #3

见附件

样例输出 #3

见附件

样例 #4

样例输入 #4

2 1 4
1 4

样例输出 #4

2
AB
AC
BA
BB

提示

对于所有测试点，$1\leq\sum n\leq 2\times 10^6$，$1\leq\sum n^2\leq10^7$。

对于所有数据，$2\leq n\leq1000$，$1\leq p\leq n^2$。

附件