Problem Description

There are $2n$ satellites, where $1 \sim n$ belong to Company A and $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 are additional requirements.

You need to assign each satellite a unique identification code of equal length, which should only contain the letters ABC. Two satellites can actually communicate if and only if their identification codes have at least one common letter. Your task is to provide a scheme that meets these requirements and output your scheme.

Input Format

This problem involves multiple test cases, read until the end of the file.

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

The next $p$ lines each contain two positive integers, indicating that these two satellites have additional requirements to be able to communicate.

Output Format

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

The next $2n$ lines each contain a string of length $m$ consisting only of the letters ABC, representing the identification codes.

Sample Input and Output

Input Sample #1

3 4 4
1 4
2 6
3 4
3 6

Output Sample #1

3
ABA
AAC
BAA
BBB
CCB
BCC

Input Sample #2

(See attachment)

Output Sample #2

(See attachment)

Input Sample #3

(See attachment)

Output Sample #3

(See attachment)

Input Sample #4

2 1 4
1 4

Output Sample #4

2
AB
AC
BA
BB

Notes

The single input file does not exceed 40MB, please use fast input and output methods.

For all test cases, $1 \leq \sum n \leq 2 \times 10^6$, $1 \leq \sum n^2 \leq 10^7$.

For all data, $2 \leq n \leq 1000$, $1 \leq p \leq n^2$.

见题面 Input 部分

见题面 Output 部分