P9924 [POI 2023/2024 R1] Satellites

Translated from [XXXI Olimpiada Informatyczna - Stage I](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Satelity](https://sio2.mimuw.edu.pl/c/oi31-1/p/sat/)。

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.

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.

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.

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$. | Subtask ID | Additional Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $n\leq100$，$M=n^2+2n$ | 7 | | 2 | $M=3n$ | 11 | | 3 | $M=n+2\lceil\log_2n\rceil$ | 23 | | 4 | $M=n+2$ | 41 | | 5 | $M=n+1$ | 18 | Translated by ChatGPT 5