{"problem":{"name":"[POI 2023/2024 R1] Satelity","description":{"content":"有 $2n$ 个卫星，$1\\sim n$ 属于 A 公司，$n+1\\sim 2n$ 属于 B 公司。 两个卫星**应当**能够通信**当且仅当**它们属于同一个公司或者有额外要求。 你需要给每个卫星分配一个等长的**独一无二**的识别码，识别码应当只包含字母 `ABC`，两个卫星**实际**能够通信**当且仅当**识别码有至少一位相同。要求你的识别码方案满足要求。输出你的方案。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9924"},"statements":[{"statement_type":"Markdown","content":"有 $2n$ 个卫星，$1\\sim n$ 属于 A 公司，$n+1\\sim 2n$ 属于 B 公司。\n\n两个卫星**应当**能够通信**当且仅当**它们属于同一个公司或者有额外要求。\n\n你需要给每个卫星分配一个等长的**独一无二**的识别码，识别码应当只包含字母 `ABC`，两个卫星**实际**能够通信**当且仅当**识别码有至少一位相同。要求你的识别码方案满足要求。输出你的方案。\n\n## Input\n\n本题多测，读入直到文件结束。\n\n对于每组数据，第一行三个正整数 $n,p,M$，其中 $M$ 意为你的识别码长度不得超过 $M$。\n\n接下来 $p$ 行，每行两个正整数，表示这两个卫星有额外要求应当能够通信。\n\n## Output\n\n对于每组数据，第一行一个正整数 $m(1\\leq m\\leq M)$，表示你的方案的识别码长度。\n\n接下来 $2n$ 行，每行一个长度为 $m$ 的只含 `ABC` 的字符串，识别码。\n\n[samples]\n\n## Background\n\n译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Satelity](https://sio2.mimuw.edu.pl/c/oi31-1/p/sat/)。\n\n## Note\n\n单个输入文件不超过 40MB，请使用较快的输入输出方式。\n\n对于所有测试点，$1\\leq\\sum n\\leq 2\\times 10^6$，$1\\leq\\sum n^2\\leq10^7$。\n\n对于所有数据，$2\\leq n\\leq1000$，$1\\leq p\\leq n^2$。\n\n| 子任务编号 | 附加限制 | 分值 |\n| :----------: | :----------: | :----------: |\n| 1 | $n\\leq100$，$M=n^2+2n$ | 7 |\n| 2 | $M=3n$ | 11 |\n| 3 | $M=n+2\\lceil\\log_2n\\rceil$ | 23 |\n| 4 | $M=n+2$ | 41 |\n| 5 | $M=n+1$ | 18 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9924","tags":["POI（波兰）","2023","Special Judge","构造"],"sample_group":[["3 4 4\n1 4\n2 6\n3 4\n3 6\n","3\nABA\nAAC\nBAA\nBBB\nCCB\nBCC\n"],["见附件","见附件"],["见附件","见附件"],["2 1 4\n1 4\n","2\nAB\nAC\nBA\nBB\n"]],"created_at":"2026-03-03 11:09:25"}}