这里是，终末停滞委员会。 - المسألة

「你们……到底是谁……？」

少女笑了。

「——我们是终末停滞委员会。是一群执意守护这个已经终结的世界的，喜欢做蠢事的家伙！」

题目描述

合理主义的 Corporations——「洗钱机构」。

官僚主义的卡乌斯学院——「官僚人员」。

成果主义的苍之学园——「白衣蛮族」。

……尽管大家总是这样争吵着，可还是有需要一起出任务的时候呢。

考虑到这么长的名字谁记得住啦——为了身为选手的你方便起见，下面我们把三所学园称为 A、B、C。

三所学园共有 $n$ 名学生。任务共有两种，分别有 $m_1,m_2$ 个，对于每个任务，都指定了两名参与者 $a_i,b_i$。

对于所有任务：当两名参与者都来自学园 C 时，获得 $2$ 点收益。
仅对于第二种任务：如果两名参与者有恰好一名来自学园 C，则遭受 $1$ 点损失。若两名参与者来自同样的学园，则遭受 $2$ 点损失。

现在，某些学生入学的学园已经确定，你需要确定剩余的所有学生入学的学园，来最大化所有任务的总净收益（即，总收益减去总损失）。注意收益和损失可以叠加，例如如果完成第二种任务的两名学生都来自学园 C，则获得的净收益是 $2-2=0$。

然而，这个问题实在有些太简单了，因此我们给出正整数 $k$，接下来，把学生所属的学园对应的字母依次连接，得到一个长度为 $n$ 的仅包含 A、B、C 三种字母的字符串，你需要给出所有最大化净收益的方案中，字符串的字典序前 $k$ 小的方案。若方案数小于 $k$，则你需要给出所有方案。

输入格式

第一行包含四个非负整数 $n,m_1,m_2,k$。

第二行包含一个长度为 $n$ 的由 ABC? 组成的字符串，依次代表每名学生入学的学园。如果为 ? 则代表尚未确定。

接下来 $m_1$ 行，每行包含两个正整数 $a_i,b_i$，代表参与第一种任务的两名学生。

接下来 $m_2$ 行，每行包含两个正整数 $a_i,b_i$，代表参与第二种任务的两名学生。

输出格式

第一行包含一个整数，代表最大的总净收益。

接下来，设 $c$ 为达到最大净收益的不同方案数。输出 $\min(c,k)$ 行，每行为一个长度为 $n$ 的由 ABC 组成的字符串。其中第 $i$ 行的输出对应字典序第 $i$ 小的方案。

样例

样例输入 1

样例输出 1

4
ACBC
BCAC
CCCC

样例输入 2

样例输出 2

-4
BBABBA
BCACBC

数据范围

记 $m=m_1+m_2$。

对于所有数据：$1 \le n \le 10^5$，$0 \le m \le 10^5$，$1 \le k \le 6 \times 10^5$，$\max(n,m) \times k \le 10^7$。

子任务 1（2 分）：$m = 0$；
子任务 2（7 分）：$n \le 15$；
子任务 3（8 分）：$n \le 2 \times 10^4$，所有的任务都是第一种任务；
子任务 4（9 分）：$n \le 2 \times 10^4$，初始时，没有任何学生入学的学园已经确定；
子任务 5（24 分）：$n \le 2 \times 10^4$，所有的任务都是第二种任务；
子任务 6（20 分）：$n \le 2 \times 10^4$，$k=1$；
子任务 7（18 分）：$n \le 2 \times 10^4$；
子任务 8（12 分）：无特殊限制。

本题有 Special Judge，如果输出正确的最大收益和错误的方案，也可以获得对应子任务 $50\%$ 的分数。如果你只希望获得这 $50\%$ 的分数，一种方法是在第一行输出最大收益之后，后续不再输出其它内容。

后记

「所以啊——」

这会成为对你的祈愿诅咒。我深信不疑。

「——你只要做你自己就好。不去当什么轻小说的主角，也可以哦。」

他瞪大了眼睛。从他的眼角，大颗的泪珠滚落而下。

——「啪咔」。

那是他手掌中，小小的手枪碎裂的声音。

QOJ.ac

QOJ

#14583. 这里是，终末停滞委员会。