Let \(M\) be the greatest value in all of \(A_i,B_i,C_i\).

[1] A new option

Consider relaxing the first and second conditions into the following.

• It can be obtained as follows: start with an empty set, and for each \(i=1,2,\dots,N\) in this order, add \(A_i\), \(B_i\), or nothing to the set.
• It can be obtained as follows: start with an empty set, and for each \(i=1,2,\dots,N\) in this order, add \(A_i\), \(C_i\), or nothing to the set.

In this case, the sought set can be constructed based on the maximum flow in the following network with \(2+2N+2M\) vertices. The number of elements in a set constructed in this way gives an upperbound to the number of elements in a set satisfying the conditions in the original problem.

• Vertex \(S\) is the source, and vertex \(T\) is the sink.
• Vertex \(i\ (1\leq i \leq N)\) corresponds to choosing \(A_i\) or \(B_i\), and vertex \(N+i\ (1\leq i \leq N)\) corresponds to choosing \(A_i\) or \(C_i\).
• Vertices \(2N+A_i\) and \(2N+B_i\) correspond to \(A_i\) and \(B_i\), respectively, and vertices \(2N+M+A_i\) and \(2N+M+C_i\) correspond to \(A_i\) and \(C_i\), respectively.
• For \(1\leq i \leq N\), there are edges of capacity \(1\) from vertex \(1\) to vertices \(2N+A_i\) and \(2N+B_i\).
• For \(1\leq i \leq N\), there are edges of capacity \(1\) from vertices \(2N+M+A_i\) and \(2N+M+C_i\) to vertex \(N+i\).
• For \(1 \leq x \leq M\), there is an edge of capacity \(1\) from vertex \(2N+x\) to vertex \(2N+M+x\).

Below is a network for \(A, B, C\) in Sample 1 (the labels of vertices are modified to be more descriptive).

If we are to construct a set satisfying the conditions in the original problem, we are in trouble with \(i\) such that both \(2N+A_i\) and \(2N+B_i\) are without flow. Below, a vertex \(i\) for such an \(i\) is called no-selection vertex (the same goes for vertex \(N+i\) for \(i\) such that both \(2N+M+A_i\) and \(2N+M+C_i\) are without flow).

In the figure below, no-selection vertices for a flow along the path \(B_3 \rightarrow 3 \rightarrow 3 \rightarrow A_3 \)or \(C_3 \rightarrow T\) are shown as squares.

[2] The relation between augmenting paths and no-selection vertices

The maximum flow in a network can be constructed by repeatedly sending flow along an augmenting path from \(S\) to \(T\) in the residual network, with reverse edges for the edges with flow. When we send flow along an augmenting path, how will the set of no-selection vertices change?

Actually, if we send flow along a shortest (with the fewest number of edges) \(S-T\) path, there will be no new no-selection vertices.

To prove this, let us show this: (there is an augmenting path such that there will be a new no-selection vertex if we send flow along that path) \(\implies\) (there is a shorter augmenting path).

Consider the example below. If we send flow along the red augmenting path, “A5orB5” will be a new no-selection vertex. However, this vertex should have no flow, so we can use the blue augmenting path instead. This path is shorter than the red one.

Let us generalize this. Assume that if we send flow along some augmenting path, vertex \(i\) will be a new no-selection vertex. Then, the augmenting path has the form \(S \rightarrow \dots \rightarrow N+j \rightarrow 2N+M+x \rightarrow 2N+x \rightarrow \dots \rightarrow T\ (x \in \{A_i,B_i\})\). Here, from the definition of no-selection vertex, vertex \(i\) should have no flow, so we can take the augmenting path \(S \rightarrow i \rightarrow 2N+x \rightarrow \dots \rightarrow T\). There are at least four edges from vertex \(S\) to vertex \(N+j\), so this augmenting path is shorter than the original one. Also, we can similarly take a shorter augmenting path even if the vertex to be the new no-selection vertex is vertex \(N+i\).

Thus, we have (there is an augmenting path such that there will be a new no-selection vertex if we send flow along that path) \(\implies\) (there is a shorter augmenting path), so if we take a shortest augmenting \(S-T\) path and send flow along it, there will be no new no-selection vertices.

Dinic’s algorithm, which finds the maximum flow and is available in AtCoder Library, uses shortest augmenting paths, so it can send flow without creating new no-selection vertices.

[3] Solution

If we start with a residual network without no-selection vertices and use the observation in [2], the maximum flow considered in [1] can restore a set that achieves the upperbound and satisfies the first and second conditions.

To start with such a residual network, we should take a set that satisfies the first and second conditions and send the corresponding flow beforehand. Clearly, \(\{A_1,A_2,\dots,A_N\}\) is one such set.

Therefore, the problem can be solved in \(O(N\sqrt{N})\) time.