Subtask 1

We can model the intersections and roads as an undirected graph. In this subtask, the roads connecting intersection ~i~ with intersection ~i+1~ for all ~1 \le i < N~ ensure that the graph is connected and has a Hamiltonian path ~1 \leftrightarrow 2 \leftrightarrow \dots \leftrightarrow N~.

First, observe that Alanna must paint at least ~N-1~ roads. If not, then the coloured roads will not form a connected subgraph. Because the original graph is connected, there must be a grey road connecting two different components of coloured roads, and there is no coloured path connecting the endpoints of this grey road.

Because we're guaranteed a Hamiltonian path ~1 \leftrightarrow 2 \leftrightarrow \dots \leftrightarrow N~, let's consider choosing these ~N-1~ roads to paint. Thinking about what constraints on the colours are necessary to satisfy the condition in the problem, we can realize that it suffices to colour the roads alternating between red and blue along the path ~1 \leftrightarrow 2 \leftrightarrow \dots \leftrightarrow N~.

Subtask 2

In this subtask, the graph is connected and has an equal number of edges and nodes. In other words, the graph forms a pseudotree. In particular, there is exactly one simple cycle in the graph.

Just like in subtask ~1~, it can be proven that Alanna must paint at least ~N-1~ roads. To achieve this bound, we can colour the edges of the cycle by alternating between red and blue, leaving exactly one cycle edge grey. The other edges should be coloured red or blue arbitrarily.

This cycle may be found by a carefully implemented graph-traversal algorithm like BFS or DFS.

Subtask 3

In this subtask, the graph is no longer guaranteed to be connected. The condition of no road belonging to two or more simple cycles can be rephrased as each connected component of the graph being a cactus graph.

By generalizing the ideas from subtasks ~1~ and ~2~, the coloured edges should form a spanning forest of the graph. That would ensure that the coloured edges form the same connected components as the original graph while colouring the minimum number of edges to meet this requirement.

Let's consider choosing an arbitrary spanning forest of the graph to colour with red or blue. For each grey edge ~u \leftrightarrow v~ not in the spanning forest, we can colour the path (in the corresponding tree) connecting ~u~ and ~v~ by alternating between red and blue. Because the component is a cactus, these paths do not share any edges, so we don't have to worry about these edges being involved in conflicting constraints.

An arbitrary spanning forest can be found with algorithms like BFS or DFS. To determine the correct colours, we cannot afford to spend ~O(N)~ time per path because there could be as many as ~\frac{N-1}{2}~ grey edges. Instead, we need to identify the corresponding path in ~O(\text{length of path})~ time. One way to do this is by first precomputing parents and depths of each node within a tree. Then, for each grey edge ~u \leftrightarrow v~, trace out the path by repeatedly moving the deeper node (~u~ or ~v~) up to its parent until ~u~ and ~v~ coincide.

Subtask 4

The solution from subtask ~3~ no longer works because the paths induced by each grey edge are no longer disjoint, so it is possible that they cause some conflicting constraints on the colours. It is no longer enough to take an arbitrary spanning forest.

Guided by these intuitions, let's think about what conditions on the spanning forest would be nice to have. Let's focus on a single connected component, where the coloured edges form a tree, and let's root the tree arbitrarily. Consider a grey edge ~u \leftrightarrow v~, and let the LCA (lowest common ancestor) of ~u~ and ~v~ in the tree be ~l~. The constraints on the colours that this grey edge places are that (1) all edges between ~u~ and ~l~ must be different from its parent edge, (2) all edges between ~v~ and ~l~ must be different from its parent edge, and (3) if ~u \ne l~ and ~v \ne l~, then two child edges of ~l~ are different.

Intuitively, most constraints are from types (1) and (2). It is actually possible to satisfy all type (1) and (2) constraints by colouring each edge by the parity of its depth in the tree, but this fails to satisfy any type (3) constraints. This motivates us to consider: Is there a spanning forest where we end up with no type (3) constraints?

In other words, we want a spanning forest with no cross edges: edges that do not connect an ancestor with a descendent. For undirected graphs, the DFS tree (tree formed by a depth-first traversal) has exactly this property we're looking for. This results in a very short solution to the full problem: For each connected component, take a DFS tree and colour the tree edges red or blue based on the parity of its depth.