建出一个 $n$ 个点的图表示 $n$ 种卡牌，两个点之间连边当且仅当两种卡牌能够匹配（存在至少一个属性值相同）。

不失一般性地，假设整张图是一个联通块。

性质：存在一个生成树，使得每个点的儿子数量 $\le 3$。

考虑如下构造方法，一个 $\text{dfs}(u)$，然后每次任意找三个儿子，保证之前没访问过：

• $v_1$，使得 $a_{v1}=a_u$；
• $v_2$，使得 $b_{v2}=b_u$；
• $v_3$，使得 $c_{v3}=c_u$。

然后直接让 $u$ 的三个儿子就是 $v_1,v_2,v_3$，如果某个 $v$ 不存在，那就不连那个儿子。

这样显然是正确的，因为如果 $a_v=a_u$ 的 $v$ 有多个，我们可以任意找一个 $v$，然后 $\text{dfs}(v)$ 下去，在 $v$ 的 dfs 过程中可以找到其他 $=a_u$ 的 $v$。

这样我们就构造出了一个生成树。

性质：对于一个大小为 $n$ 的子树，如果 $n$ 为偶数，那么子树内卡牌可以两两匹配。否则这个子树的根会剩下一张卡牌未匹配，其他两两匹配。而且这样是最优的。

显然，如果 $n$ 是奇数，那么总牌数 $3n$ 也是奇数，那么最优情况下也会剩下一个牌没有匹配。

考虑以下算法：当前在点 $u$。我们看它的至多三个儿子是否有剩卡牌，如果有就直接匹配，因为儿子数量 $\le 3$，所以一定能匹配。

此时 $u$ 剩下的卡牌数如果 $\ge 2$，那他就自己和自己匹配，让卡牌数 $-=2$，那么此时 $u$ 剩下的卡牌数就是 $0$ 或 $1$，取决于 $sz[u]$ 的奇偶性。

这样我们就构造出了最优情况。