For edges with \(c_{a_i} \neq c_{b_i}\), we can easily select the direction.

For edges with \(c_{a_i} = c_{b_i}\), which means there are equal numbers of vertices reachable from \(a_i\) and \(b_i\), it must be reachable from \(a_i\) to \(b_i\) and vice versa, that is, they must be strongly connected.

Thus, the problem can be rephrased as one where we are given a connected undirected graph and asked to direct the edges so that the graph becomes strongly connected.

Actually, we can do it as follows: make a DFS tree, direct each edge in the tree away from the root, and direct the edges not in the tree towards the root. The highlights of the proof of this method are:

• showing that the graph has no bridge;
• showing that the root is reachable from every vertex, by paying attention to the lowlinks.

Our intended solution takes \(O(N + M)\) time under the constraint that guarantees the existence of a solution, and \(O(N + M + \frac{N(N + M)}{\sigma})(\sigma: \mathrm{wordsize})\) time without this constraint.