Background

Translated from XXXI Olimpiada Informatyczna - Stage I Satelity。

Problem Description

There are $2n$ satellites. Satellites $1\sim n$ belong to company A, and satellites $n+1\sim 2n$ belong to company B.

Two satellites should be able to communicate if and only if they belong to the same company, or there is an additional requirement.

You need to assign each satellite a unique identification code of the same length. The code must contain only the letters ABC. Two satellites can actually communicate if and only if their codes have at least one position with the same letter. Your coding scheme must satisfy the requirements. Output your scheme.

Input Format

This problem has multiple test cases. Read until end of file.

For each test case, the first line contains three positive integers $n,p,M$, where $M$ means the length of your identification codes must not exceed $M$.

The next $p$ lines each contain two positive integers, meaning that these two satellites have an additional requirement and should be able to communicate.

Output Format

For each test case, the first line contains a positive integer $m(1\leq m\leq M)$, meaning the length of the identification codes in your scheme.

The next $2n$ lines each contain a string of length $m$ consisting only of ABC, which is the identification code.

3 4 4
1 4
2 6
3 4
3 6

3
ABA
AAC
BAA
BBB
CCB
BCC

见附件

见附件

见附件

见附件

2 1 4
1 4

2
AB
AC
BA
BB

Hint

A single input file does not exceed 40MB. Please use fast input and output methods.

Constraints: for all test points, $1\leq\sum n\leq 2\times 10^6$, $1\leq\sum n^2\leq10^7$.

For all testdata, $2\leq n\leq1000$, $1\leq p\leq n^2$.

Translated by ChatGPT 5