Alternating Path

Research summary: I checked the official Codeforces problem/editorial material and an external CF Step explanation/code page first. The official editorial page currently exposes the accepted model solution while the prose tutorial is basically a placeholder; CF Step's hints and model code point to the same intended approach: bipartite-color each component and add the larger color class if the component is bipartite. Sources used: problem statement, official editorial page, CF Step hints, CF Step code.

The key phrase is all paths, not necessarily simple. Since vertices can repeat, this really means every possible walk starting from a vertex has to obey the alternating direction pattern. That is a very strong condition.

Fix a vertex $s$ and suppose it is beautiful.

First, consider any neighbor $u$ of $s$. The path $s \to u$ has length $1$, and the first edge of an alternating path must be directed from the first vertex to the second. Therefore every edge incident to $s$ must be directed out of $s$.

Now take a path $s \to u \to x$. The second edge must be traversed against its direction, so the edge $(u,x)$ must be directed from $x$ to $u$. Since $x$ could be any neighbor of $u$, every edge incident to $u$ must be directed into $u$.

Continue this along any shortest path from $s$. If a vertex $v$ is at distance $d$ from $s$, then:

• if $d$ is even, every edge incident to $v$ must point out of $v$;
• if $d$ is odd, every edge incident to $v$ must point into $v$.

So vertices get forced into two roles: "all outgoing" and "all incoming". No negotiation, no clever hack, no graph-matching magic despite the tag trying to look fancy.

Now look at an edge $(a,b)$. If $a$ and $b$ have the same distance parity from $s$, then they demand the same role. If both are "all outgoing", the edge would need to point away from both endpoints. If both are "all incoming", it would need to point into both endpoints. Both are impossible.

Therefore, if $s$ is beautiful, every edge in its connected component must connect opposite distance parities. That means the connected component is bipartite.

This proves an important upper bound:

$$\text{non-bipartite component contributes } 0.$$

If a non-bipartite component had even one beautiful vertex, the argument above would force the whole component to be bipartite, contradiction.

Now suppose a connected component is bipartite, with color classes $A$ and $B$. If we orient every edge from $A$ to $B$, then every vertex in $A$ is beautiful:

• step $1$ goes from $A$ to $B$ along the edge direction;
• step $2$ goes from $B$ to $A$ against the edge direction;
• step $3$ goes from $A$ to $B$ along the edge direction;
• and so on.

Because every walk in a bipartite graph alternates between $A$ and $B$, this direction pattern works for every possible walk starting from any vertex in $A$.

If we reverse all directions, then all vertices in $B$ become beautiful instead. So for this component, the best possible number of beautiful vertices is:

$$\max(|A|, |B|).$$

Connected components are independent because there are no edges between them. So the final answer is:

$$\sum_C \begin{cases} \max(c_0(C), c_1(C)), & C \text{ is bipartite}, \\ 0, & C \text{ is not bipartite}. \end{cases}$$

An isolated vertex is just a bipartite component with sizes $1$ and $0$, so it contributes $1$. That also matches the intuition: with no edges, there is nothing to violate.

Implementation:

1. Build the undirected graph.
2. Run BFS/DFS from each unvisited vertex.
3. Assign colors $0/1$ like a normal bipartite check.
4. Count the two color classes inside the component.
5. If a conflict appears, add $0$ for that component; otherwise add $\max(c_0,c_1)$.

Complexity:

$$O(n+m)$$

per test case, with $O(n+m)$ memory. Across all test cases this is safe because the total $n$ and total $m$ are each at most $2 \cdot 10^5$.