Two telecommunications companies from Byteland will soon place $n$ satellites each into orbit to provide Internet access to the entire country. The satellites of the first company will be numbered from $1$ to $n$, while the satellites of the second company will be numbered from $n + 1$ to $2n$.

For the system to function correctly, every pair of satellites belonging to the same company must establish direct communication with each other. Although the companies will compete for customers, they have decided that in case of unforeseen failures, some pairs of satellites belonging to different companies will also establish direct communication.

Each satellite must now be assigned a unique identification code, which is a sequence of $m$ letters from the set $\{A, B, C\}$. Which satellites will communicate with each other will depend on their codes: a satellite with code $a_1a_2 \dots a_m$ will communicate with a satellite with code $b_1b_2 \dots b_m$ if and only if these codes have the same letter at at least one position (i.e., there exists $1 \le i \le m$ such that $a_i = b_i$).

Your task is to assign codes to the satellites.

Input

The first line of input contains three integers $n$, $p$, and $M$ ($2 \le n \le 1000$, $1 \le p \le n^2$), representing the number of satellites for each company, the number of required connections between satellites of different companies, and the limit on the length of the codes.

The next $p$ lines contain descriptions of the connections: the $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n < b_i \le 2n$), indicating that the satellites with numbers $a_i$ and $b_i$ must establish a direct connection.

Output

Your program should output in the first line a single integer $m$ ($1 \le m \le M$) representing the length of the identification codes assigned to the satellites.

In the next $2n$ lines, you must output the codes; the $i$-th of these lines should contain a sequence of $m$ letters from the set $\{A, B, C\}$, which is the code assigned to satellite number $i$.

All codes must be pairwise distinct, and the pairs of satellites that establish connections must correspond to the requirements from the input.

Examples

Input 1

3 4 4
1 4
2 6
3 4
3 6

Output 1

3
ABA
AAC
BAA
BBB
CCB
BCC

Note 1

Satellite number 1 is assigned the code ABA, while satellite number 4 is assigned the code BBB; they communicate with each other because they have the same letter B at the second position in their codes.

Evaluation

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

Note. Changes relative to version 1.0 can be found in SIO in the Files and tests section.