Description
@足立レイ 根据官方解题报告，这道题的正解核心思路是按 k=0,1,2 三种情况分别构造，其中 k=0 是基础， k=1,2 在 k=0 的基础上扩展。下面分情况展开。
---
k=0 ：定向与染色
核心观察
当 k=0 时，删去任意一种颜色的边，得到的图都必须是一个 DAG（有向无环图）。这是因为如果删去颜色 c 的边后存在环，那么这个环只包含另外两种颜色，就是一个“不满意环”，与 k=0 矛盾。
定向构造
令 G_c 为删去所有颜色为 c 的边得到的图， p_c 为 G_c 的拓扑序， \mathrm{rk}_c 为对应的排名序列。
对于原图中的边 x \xrightarrow{c} y ，在另外两个排列 p_{(c+1)\bmod 3} 和 p_{(c+2)\bmod 3} 中， x 都排在 y 前面。因此，至少存在两个颜色 c' 满足 \mathrm{rk}_{c',x} < \mathrm{rk}_{c',y} 。
采取摩尔投票策略：
F(x,y) = [\mathrm{rk}_{1,x} < \mathrm{rk}_{1,y}] + [\mathrm{rk}_{2,x} < \mathrm{rk}_{2,y}] + [\mathrm{rk}_{3,x} < \mathrm{rk}_{3,y}]
· 若 F(x,y) \ge 2 且 F(y,x) \le 1 ，则方向为 x \to y ；
· 若 F(x,y) \le 1 且 F(y,x) \ge 2 ，则方向为 y \to x 。
由于 F(x,y) + F(y,x) = 3 ，上述条件恰好覆盖所有情况，方向可以唯一确定。
染色还原
仅通过三个排名序列 \mathrm{rk}_1, \mathrm{rk}_2, \mathrm{rk}_3 即可还原颜色：
· 若 F(x,y) = 2 ，则边 x \to y 的颜色设为唯一满足 \mathrm{rk}_{c,x} > \mathrm{rk}_{c,y} 的颜色 c ；
· 若 F(x,y) = 3 ，任意设置颜色均可。
正确性证明
若存在一个简单环只包含颜色 c 和 (c+1)\bmod 3 ，记 q = \mathrm{rk}_{(c+2)\bmod 3} ，则环上应有 q_{a_1} < q_{a_2} < \cdots < q_{a_l} < q_{a_1} ，矛盾。因此所有简单环都包含三种颜色，满足 k=0 的条件。
信息量
传输三个排列的排名序列，信息量为：
\log_2((n!)^3) = 3n\log_2 n - 3(\log_2 e)n + o(n)
当 n=300 时约需 6123.83 比特。
---
k=1 ：环的修正
结构观察
当 k=1 时，删去任意一种颜色后，得到的图的每个强连通分量都是一个环。
令 G_c 为删除颜色 c 后的图。对 G_c 的每个环，若反转环上一条边的方向，则可以得到一个 DAG。因此存在一个拓扑序，使得每个环上的点在拓扑序上构成一段区间 [l, r] ，且反转方向的边恰好是 r \to l 。
扩展构造
在 k=0 的基础上，额外传递每个环的信息用于修正答案：
· 传递一个 01 序列 a_c ，其中每段取值为 1 的区间 [l, r) 对应一个环的拓扑序区间 [l, r] ；
· 由于每个环的长度至少为 3，可以通过 a_c 唯一确定所有环。
信息量
直接传输 a_0, a_1, a_2 的信息量为：
\log_2((n!)^3) + 3n = 3n\log_2 n + 3(1 - \log_2 e)n + o(n)
---
k=2 ：更复杂的修正
官方报告中 k=2 的部分涉及更复杂的结构分析和修正编码。从已有信息推断， k=2 时删去任意颜色后的图不再是简单的环结构，可能需要传递更多关于“例外边”的信息来修正 k=0 的构造。具体细节需要查阅报告的后续页面。
---
总结
这道题的解法链条是：
1. k=0 建立基准：用三个 DAG 的拓扑序 + 摩尔投票确定方向和颜色，信息量 \sim 3n\log_2 n ；
2. k=1 修正环：额外传递每个环的区间信息，信息量增加 3n 比特；
3. k=2 进一步修正：需要处理更一般的强连通分量结构。
核心洞察是：不满意环的数量限制，本质上等价于删去单色边后图的有环性限制。 k=0 对应无环（DAG）， k=1 对应只有简单环， k=2 对应更复杂的结构。整个方案通过“拓扑序 + 修正信息”的框架统一处理。
