\(M\) を \(A_i,B_i,C_i\) の最大値とします。

[1] \((A_i,B_i)\ (A_i,C_i)\) どちらも加えなくてもいいとした場合

\(1,2\) 番目の条件を以下のように緩和した場合を考えます。

• 空集合からはじめて \(i=1,2,\dots,N\) の順に「 \(A_i,B_i\) のいずれかを追加するか、いずれも追加しない」ことで得られる集合である。
• 空集合からはじめて \(i=1,2,\dots,N\) の順に「 \(A_i,C_i\) のいずれかを追加するか、いずれも追加しない」ことで得られる集合である。

この場合は以下のような \(2+2N+2M\) 頂点のネットワークグラフでの最大流をもとに条件を満たす集合が構築できます。このようにして構築された集合の要素数は、元問題の条件を満たす集合の要素数の上界になっています。

• 頂点 \(S\) を始点、頂点 \(T\) を終点とする。
• \(A_i\) または \(B_i\) を選ぶことに対応する頂点を頂点 \(i\ (1\leq i \leq N)\) とし、\(A_i\) または \(C_i\) を選ぶことに対応する頂点を頂点 \(N+i\ (1\leq i \leq N)\) とする。
• \(A_i,B_i\) に対応する頂点を頂点 \(2N+A_i,2N+B_i\) とし、頂点 \(A_i,C_i\) に対応する頂点を頂点 \(2N+M+A_i,2N+M+C_i\) とする。
• \(1\leq i \leq N\) について、頂点 \(S\) から頂点 \(i\) 、頂点 \(N+i\) から頂点 \(T\) へ容量 \(1\) の辺を張る。
• \(1\leq i \leq N\) について、頂点 \(i\) から頂点 \(2N+A_i,2N+B_i\) へ容量 \(1\) の辺を張る。
• \(1\leq i \leq N\) について、頂点 \(2N+M+A_i,2N+M+C_i\) から頂点 \(N+i\) へ容量 \(1\) の辺を張る。
• \(1 \leq x \leq M\) について、頂点 \(2N+x\) から頂点 \(2N+M+x\) へ容量 \(1\) の辺を張る。

下図はサンプル \(1\) の \(A,B,C\) に対して構築されたネットワークグラフです（頂点ラベルは実態がわかりやすくなるようなものに変えています）。

元問題の条件を満たす集合を、上記のグラフにおける最大流をもとに構築しようとしたとき、頂点 \(2N+A_i,\ 2N+B_i\) のいずれにもフローが流れていないような \(i\) が問題になります。以下、そのような \(i\) に対する頂点 \(i\) を no selection vertex とよびます（頂点 \(2N+M+A_i,2N+M+C_i\) のいずれにもフローが流れていない \(i\) に対する頂点 \(N+i\) についても同様）。

下図の例では \(S \rightarrow A_3 \)or \(B_3 \rightarrow 3 \rightarrow 3 \rightarrow A_3 \)or \(C_3 \rightarrow T\) というパスに沿ったフローが流れているときの no selection vertex が四角であらわされています。

[2] 増加パスと no selection vertex の関係

ネットワークグラフにおいて最大流は、現在フローが流れている部分について逆辺を張った残余グラフにおいて、\(S\) から \(T\) にいたる増加パスに沿ってフローを流していくことで構築できます。増加パスに沿ってフローを流した際、no selection vertex からなる集合はどう変化するでしょうか？

実は増加パスのうち（辺の数の意味で）\(S-T\) 最短になっているものに沿ってフローを流した場合、新たに no selection vertex となるような頂点は存在しません。

このことを証明するために、「ある増加パスにそってフローを流すと新たに no selection vertex となる頂点が存在する \(\implies\) より短い増加パスが存在する」が成り立つことを示します。

具体例を考えてみましょう。下図の例では赤い増加パスに沿って流す際、A5orB5 の頂点が新たに no selection vertex となってしまっています。しかし、 A5orB5の頂点にはフローが流れていないはずなので、青で示された増加パスに取り換えることができます。このとき、増加パスの経路長は短くなっています。

これを一般化しましょう。ある増加パスに沿ってフローを流したとき頂点 \(i\) が新たな no selection vertex となるとします。このとき、増加パスは \(S \rightarrow \dots \rightarrow N+j \rightarrow 2N+M+x \rightarrow 2N+x \rightarrow \dots \rightarrow T\ (x \in \{A_i,B_i\})\) という形になっています。このとき no selection vertex の定義から、頂点 \(i\) へはフローが流れていないはずなので、\(S \rightarrow i \rightarrow 2N+x \rightarrow \dots \rightarrow T\) という増加パスが取れます。頂点 \(S\) から頂点 \(N+j\) に至るまでの辺の数は \(4\) 以上であるため、この増加パスはもとの増加パスより短くなっています。また、新たに no selection vertex となるのが頂点 \(N+i\) の場合も同様により短い増加パスが取れます。

以上より「ある増加パスにそってフローを流すと新たに no selection vertex となる頂点が存在する \(\implies\) より短い増加パスが存在する」が成り立つので、増加パスとして \(S-T\) 最短であるものをとってフローを流した場合、新たに no selection vertex となるような頂点は存在しません。

最大流問題を解くアルゴリズムとして AtCoder Library にも実装されている Dinic 法は \(S-T\) 最短な増加パスに沿って流すアルゴリズムなので、Dinic 法を用いた場合は新たに no selection vertex を増やすことなくフローを流せます。

[3] 解法

[2] の考察から [1] で考えたフローは初期状態で no selection vertex が存在しないような残余グラフから始めれば、上界を達成しつつ \(1,2\) 番目の条件を満たす集合が復元できることがわかります。

これは \(1,2\) 番目の条件を満たす集合をとってそれに対応するフローをあらかじめ流せばいいですが、明らかに \(\{A_1,A_2,\dots,A_N\}\) が条件を満たします。

以上よりこの問題は \(O(N\sqrt{N})\) の計算量で解くことができます。