In the following, we denote an edge from \(a\) to \(b\) as \((a,b)\). We also denote \((a,b)\) and \((b,a)\) together as \([a,b]\).

If the given graph contains both edges \((a,b)\) and \((b,a)\), the answer is clearly No. In the following, we consider the other inputs.

First, consider the case where the given graph is a tournament.

We use the following lemma.

Lemma: For four vertices \(a,b,c,d\), we can reverse just \([a,b],[b,c],[c,d],[d,a]\).

Proof of Lemma: Take a subset \(X\) of size \(K-2\) that does not contain \(a\), \(b\), \(c\), or \(d\). Perform the operations in the order \(S=X\cup \lbrace a,b \rbrace,X\cup \lbrace b,c \rbrace,X\cup \lbrace c,d \rbrace,X\cup \lbrace d,a \rbrace\). (End of proof)

When \(K\) is even, by applying mathematical induction using Lemma 2 below, we can show that the answer is always Yes.

Lemma 2: If \(K\) is even, for three vertices \(a,b,c\), we can reverse just \([a,b],[b,c]\).

Proof of Lemma 2: Take a subset \(Y\) of size \(K-2\) that does not contain \(a\), \(b\), or \(c\). Perform the operations in the order \(Y\cup\lbrace a,b\rbrace, Y\cup \lbrace b,c\rbrace\). The edges reversed other than \([a,b],[b,c]\) form a complete bipartite graph with one endpoint being \(a\) or \(c\) and the other being a vertex in \(Y\). This complete bipartite graph can be decomposed into some number of cycles of length \(4\) (since \(|Y|=K-2\) is even). Thus, by applying the lemma, we can reverse just \([a,b],[b,c]\). (End of proof)

If \(K\) is odd, since operations do not change the parity of each vertex’s out-degree, a necessary condition for the answer to be Yes is that the number of vertices with even out-degree is \(\lceil \frac{N}{2}\rceil\).

In fact, this is also sufficient, which can be proved by applying mathematical induction using the lemma.

If the input is not a tournament, taking the complement graph of the input (where the complement graph is undirected) and mapping the parity of each vertex’s current out-degree (in the input graph) to white and black, we reduce to the following problem:

We are given a graph with \(N\) vertices where each vertex is colored white or black. For each edge, perform an operation that flips the color of one of its endpoints. Determine whether we can make the number of black vertices equal to a specified value.

Consider the case where the graph is connected. Taking a spanning tree and directing the non-tree edges toward the root, we can freely choose the colors for all vertices except the root. Also, since the sum of out-degrees is fixed, once the colors of the non-root vertices are determined, the root’s color is uniquely determined. This shows that only the parity of the number of vertices whose color can be changed is determined. (Related problem: AGC 035-B Even degrees)

For the disconnected case, we process each connected component as above and determine whether we can make the total equal to the required value.

All we need is the number of vertices and edges in each connected component of the complement graph, which can be obtained via complement BFS.

(Further analysis shows that when the input graph is sparse, the answer is always Yes, and it can be said that performing complement BFS naively causes no issues.)