In the State of Takahashi in AtCoderian Federation, there are N cities, numbered 1, 2,…
- User
In the State of Takahashi in AtCoderian Federation, there are N cities, numbered 1, 2, ..., N. M bidirectional roads connect these cities. The i-th road connects City A_i and City B_i. Every road connects two distinct cities. Also, for any two cities, there is at most one road that directly connects them.
One day, it was decided that the State of Takahashi would be divided into two states, Taka and Hashi. After the division, each city in Takahashi would belong to either Taka or Hashi. It is acceptable for all the cities to belong Taka, or for all the cities to belong Hashi. Here, the following condition should be satisfied:
- Any two cities in the same state, Taka or Hashi, are directly connected by a road.
Find the minimum possible number of roads whose endpoint cities belong to the same state. If it is impossible to divide the cities into Taka and Hashi so that the condition is satisfied, print
-1.Constraints
- 2 \leq N \leq 700
- 0 \leq M \leq N(N-1)/2
- 1 \leq A_i \leq N
- 1 \leq B_i \leq N
- A_i \neq B_i
- If i \neq j, at least one of the following holds: A_i \neq A_j and B_i \neq B_j.
- If i \neq j, at least one of the following holds: A_i \neq B_j and B_i \neq A_j. Input
Input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 : A_M B_M
Output
Print the answer.
Examples
Input
5 5 1 2 1 3 3 4 3 5 4 5
Output
4
Input
5 1 1 2
Output
-1
Input
4 3 1 2 1 3 2 3
Output
3
Input
10 39 7 2 7 1 5 6 5 8 9 10 2 8 8 7 3 10 10 1 8 10 2 3 7 4 3 9 4 10 3 4 6 1 6 7 9 5 9 7 6 9 9 4 4 6 7 5 8 3 2 5 9 2 10 7 8 6 8 9 7 3 5 3 4 5 6 3 2 10 5 10 4 2 6 2 8 4 10 6
Output
21
Assistant
We need to parse the problem. There are N cities, M roads. After dividing cities into two groups (call them T and H), the condition: Any two cities in the same state are directly connected by a road. That is, within each group, every pair of cities must have a direct road connecting them. In other words, each group must be a clique (complete graph) in the original graph. We need to assign each node to either group (maybe all in one group) such that both groups induce cliques. The goal: minimize the number of roads whose both endpoints belong to the same state. Equivalent: We count the edges that are internal to groups (i.e., edges that have both ends in T or both in H). We want to minimize that number.
But wait: The condition says: "Any two cities in the same state, Taka or Hashi, are directly connected by a road." That means within each group, the induced subgraph must be a complete graph. So for any two nodes that are both in T, there must be an edge between them. Similarly for H. This imposes constraints on possible partitions: The two groups must be cliques. That is, the complement of the graph? Actually the condition requires that all possible edges within each group exist in the original graph. So we must choose a partition (two cliques covering all vertices) such that the two cliques are possibly overlapping? They are disjoint because each city belongs to exactly one state, so the partition is a bipartition of the vertex set into two cliques (maybe one side empty, which is trivially a clique with 0 or 1 vertices? But with 0 or 1 nodes, any set of size ≤1 is vacuously a clique. However, the problem says it's acceptable for all cities to belong to T or all to H. So yes, empty or single node sets are cliques.)
Thus we need to partition the vertex set V into two disjoint subsets T and H (V = T ∪ H, T ∩ H = ∅) such that T induces a clique and H induces a clique.
Now among all such partitions, we want to minimize the number of edges whose both endpoints are in the same state, i.e., |E(T)| + |E(H)|, where E(S) denotes edges inside S.
Since total edges M is fixed, minimizing internal edges is equivalent to maximizing edges crossing between T and H? Actually M = internal_edges + crossing_edges. So minimizing internal edges is same as maximizing crossing edges. But we must satisfy clique constraints.
We need to find if there exists any such bipartition into two cliques. If not, answer -1. Else find min internal edges.
Observations: The condition that both sides are cliques implies that the complement of the graph must be a graph that is "bipartite"? Let's think: In the complement graph, edges represent missing edges. In the original graph, we require that within each part there are no missing edges. That is, in the complement graph, there should be no edge inside either part. In other words, the complement graph's edges can only go between the two parts. So the partition must be a bipartition such that the complement graph is bipartite with the same partition? Actually, we require that for any two vertices in the same part, the edge exists in original, so in complement there is no edge between them. So the complement graph is a subgraph of the complete bipartite graph between T and H. That means the complement graph must be bipartite, with the bipartition (T, H) being a valid bipartition for the complement? But careful: The complement graph has edges exactly for non-edges of original. The condition is: For any u, v in T, (u, v) must be an edge in original, so (u, v) is NOT an edge in complement. Similarly for H. So in complement, there are no edges within T or within H. So complement edges only exist between T and H. Therefore, the complement graph is bipartite (actually it's a bipartite graph, with bipartition (T, H)). But does that impose that the complement graph must be bipartite in the first place? For a partition to exist, we need to assign nodes to two sides such that the complement graph has no edges inside either side. That's essentially saying that the complement graph must be 2-colorable? Because we are coloring nodes with two colors (say color T and H) such that every edge of complement goes across the colors, i.e., complement must be bipartite. But wait: In a bipartite graph, we require that no edge has both ends same color. That's exactly: In complement graph, we need to 2-color its vertices such that no complement edge is monochromatic. This is the definition of a proper 2-coloring of the complement graph. So the existence of a partition into two cliques is equivalent to the complement graph being bipartite. Because if complement is bipartite, we can take one color class as T, the other as H, and then within each color class, there are no complement edges, meaning all original edges exist, so each side is a clique. Conversely, if there is a partition into two cliques, then complement edges cannot be inside either side, so they go across, so the complement is bipartite with that partition.
But there is a nuance: In a bipartite graph, we normally allow disconnected components. But the complement graph could be bipartite. However, what about nodes isolated in complement? They can go to either side. So existence of a bipartition into two cliques is exactly that the complement graph is bipartite. However, we also need to consider that the original graph may have missing edges within a group, which would violate the condition. So yes.
Therefore the problem reduces to: Given original graph G with N nodes, M edges. Let complement graph G' have edges where G has none, except that we don't include self-loops. G' has N(N-1)/2 - M edges. Determine if G' is bipartite. If not, answer -1. If yes, then there are multiple possible bipartitions (since if G' is bipartite, it may have multiple possible 2-colorings, especially if it's disconnected). Among all bipartitions (valid 2-colorings of G'), we need to minimize the number of internal edges in original graph, i.e., edges that are within the same side.
But note: In a valid coloring of G', we assign each node a color (say 0 or 1). This defines two sets S0 and S1. The condition is satisfied. We need to minimize |E(S0)| + |E(S1)|.
Since M is fixed, minimizing internal edges is equivalent to maximizing crossing edges. Crossing edges are edges of G that have endpoints in different sets. So we want to maximize the number of edges of G that are between S0 and S1.
Now, note that an edge of G is crossing if its endpoints have different colors. An edge of G' is also crossing if its endpoints have different colors (since we color vertices). But we have constraints: In any valid coloring, all edges of G' must be crossing. That is, G' edges cannot be monochromatic. So the coloring must be a proper 2-coloring of G'. That's a constraint. So we are to choose a proper 2-coloring of G' to maximize the number of G edges that go across.
Thus problem: We have two graphs on same vertex set: G (original) and G' (complement). G' is bipartite (else impossible). For each proper 2-coloring of G' (which may be many, due to components being bipartite and flippable), we need to compute the number of G edges that are cut (i.e., endpoints have different colors). We want the maximum cut among proper colorings of G'. Then answer = M - max_cross (since internal edges = M - crossing edges). But also we might have possibility to have all nodes in one side? That corresponds to one side being empty, but is that a proper coloring of G'? If one side empty, then all nodes have same color, say color 0. Then any edge of G' would be monochromatic, which is not allowed unless there are no G' edges (i.e., original graph is complete). So if G' has any edges, the all-same coloring is not allowed. But the problem says it's acceptable for all cities to belong to T or all to H. However, that scenario is only allowed if the condition is satisfied, i.e., if the set of all cities is a clique, which means original graph is complete, thus G' has no edges. In that case, all-same coloring is okay because there are no G' edges to violate. But would that be considered a proper 2-coloring of G'? Usually a proper 2-coloring requires that each edge's endpoints have different colors. If there are no edges, any assignment is trivially proper. So yes, all-same works. So the condition remains: coloring must be a proper 2-coloring of G'. So if G' is bipartite (including possibly empty), all proper 2-colorings are allowed. If G' is not bipartite, impossible => -1.
Thus we need to solve: Given a bipartite graph G' (the complement of G), and a graph G (original), find the maximum number of edges of G that go across the two sides in any proper 2-coloring of G'. This is like we have constraints that for each edge in G', the endpoints must have opposite colors. That means the colors of vertices are forced to be consistent along each connected component of G'? Actually, G' is bipartite, so each component has two possible colorings (swap sides). But also, the coloring of vertices within a component must satisfy the bipartite constraints: if you fix one vertex's color, all others are determined uniquely because bipartite graphs are 2-colorable uniquely up to swapping. So each component of G' has two possible assignments: assignment A and assignment ~A (swap colors). The overall coloring is a combination of independent choices for each component. Some components might be isolated vertices (no edges). For an isolated vertex, it is bipartite and both colors are allowed, and no constraints with others? But note: if a vertex has no edges in G', it imposes no constraints, so it can be colored arbitrarily regardless of others. However, there may be edges in G between components that we want to maximize cross.
So we have a set of N vertices partitioned into components of G' (the complement graph). Within each component, the relative colors are fixed up to a global flip. And isolated vertices are components of size 1 with no constraints, so they can be assigned either color independently.
Goal: Choose for each component a color assignment (flip or not) to maximize the number of G edges whose endpoints have different colors.
This is reminiscent of a maximum cut problem with constraints, but because each component's internal relative colors are fixed, we can treat each component as a "super-vertex" with two possible "states": either the original assignment or the flipped assignment. However, the coloring of vertices inside a component is not uniform: it assigns each vertex a specific color, not the same for all vertices in the component. So we cannot just treat the component as a whole with a single color. But we can represent each component's two possible assignments as a mapping from its vertices to {0,1}. This is essentially a "2-coloring" of that component.
We need to combine choices for each component to maximize total crossing edges of G.
We can formulate it as: For each component C, we have two possible color vectors: f_C^0 (the base assignment) and f_C^1 (the complement assignment, i.e., flip all colors). Actually, the base assignment can be arbitrarily chosen: we pick one of the two possible bipartite colorings as reference. Then for each component, we have a binary variable x_C ∈ {0,1} indicating whether we flip the component (1 means flip). Then the actual color of vertex v ∈ C is col(v) = base(v) XOR x_C.
Now consider any edge e = (u,v) in G. If u and v are in the same component of G', then because G' edges force opposite colors, what about edges of G inside the same component? They are edges that exist in G but not in G'? Wait: If u and v are in same component of G', they might be connected by some path in G', but that doesn't directly constrain G edges. However, the colors of u and v are determined: col(u) = base(u) XOR x_C, col(v) = base(v) XOR x_C. So the difference col(u) XOR col(v) = base(u) XOR base(v). Since x_C cancels. So for vertices in the same component, whether they are same or different color is fixed, independent of flipping. That's because flipping the whole component flips both, so the parity remains same. So for any pair of vertices within the same component, the relative color (same/different) is predetermined by the base coloring. This makes sense: The bipartition of the component itself gives a partition of its vertices into two internal groups. Flipping swaps which group is color 0 and which is color 1, but two vertices that were originally same group become same color after any flip? Actually, if base(u) = base(v) then after flip both are flipped, so they remain equal. If base(u) != base(v), they remain different. So indeed relative color is invariant.
Thus for edges of G that lie within a single component, whether they are crossing or not is fixed (depending on base). So those contributions to the objective are constant, unaffected by the choices of flips. Good.
Now edges of G that go between different components: suppose u ∈ C1, v ∈ C2. Then col(u) = base(u) XOR x_{C1}, col(v) = base(v) XOR x_{C2}. So col(u) XOR col(v) = base(u) XOR base(v) XOR x_{C1} XOR x_{C2}. So the condition for edge to be crossing (i.e., different colors) is col(u) != col(v) ↔ (base(u) XOR base(v) XOR x_{C1} XOR x_{C2}) = 1.
Thus for each inter-component edge, whether it is crossing depends on the XOR of the flip variables of the two components, plus a constant offset based on base colors.
We want to maximize total crossing edges, which is sum over edges of indicator that colors differ.
This is essentially a problem: We have a collection of components, each with two possible states (flip 0 or 1). The contribution of each inter-component edge can be expressed as: crossing = 1 if x_{C1} XOR x_{C2} = d_{uv} where d_{uv} = base(u) XOR base(v) XOR 1? Wait derive properly:
Define for each edge e = (u,v) between components C1 != C2, let b_u = base(u), b_v = base(v). Then crossing condition: col(u) != col(v) ⇔ (b_u ⊕ x_{C1}) != (b_v ⊕ x_{C2}) ⇔ b_u ⊕ x_{C1} ⊕ b_v ⊕ x_{C2} = 1. So we require x_{C1} ⊕ x_{C2} = 1 ⊕ b_u ⊕ b_v. Let c_{e} = 1 ⊕ b_u ⊕ b_v. So crossing = 1 if x_{C1} ⊕ x_{C2} = c_e. Equivalent: crossing = 1 if (x_{C1} ⊕ x_{C2}) = c_e.
Otherwise crossing = 0.
We want to maximize total crossing count, which includes also intra-component edges whose crossing status is fixed (constant). Let constant K = number of intra-component edges (edges within same component) that are crossing (i.e., have different colors) given the base coloring (or any because it's invariant). That's constant. And also intra-component edges that are not crossing are also constant.
So the optimization is over flip variables of components to maximize sum over inter-component edges of indicator that x_i ⊕ x_j = c_{e}.
This looks like a Max-Cut type problem but with constraints that each edge's desired parity is either 0 or 1. This is similar to "maximum agreement" with given parity constraints. Actually we can treat each inter-component edge as a constraint that gives a certain contribution if the XOR of the flip bits equals a given value. This is a kind of 2-satisfiability with optimization? Or a weighted Max-2XOR? We want to assign binary values to nodes (components) to maximize the sum of weights of edges where x_i ⊕ x_j = given parity.
This can be solved by transforming to a graph with two possible states per component: flipping the interpretation? Alternatively, note that we can treat the condition as: For each edge e with endpoints in distinct components, define w_e = 1. But the contribution is either 0 or 1. This is a binary optimization problem on a graph whose vertices are components. If we consider x_i variables, then for each edge e, the contribution is 1 if x_i ⊕ x_j = c_e else 0. That's equivalent to: contribution = (1 if x_i ⊕ x_j = c_e) = 1 - (1 if x_i ⊕ x_j ≠ c_e) maybe? But we can also think of it as: We want to maximize number of satisfied edges where satisfaction means crossing.
Alternatively, we can model as: For each component we have two possible assignments (color sets). This is like each component gives two possible "color patterns" for its vertices. But there is a more efficient method: Because N ≤ 700, the number of components is at most N. M up to ~ N(N-1)/2 (max ~ 244650). That's big but we might be able to do something like dynamic programming on components if we can treat them as nodes in a graph of moderate size? The number of components could be large though (up to N). But we can still handle O(N^2) or O(N^3) possibly? N=700, N^2=490k, N^3=343M which might be borderline but perhaps okay in C++ but Python might need O(N^2) or O(N * something). However, we need to also handle up to M edges. But we can aggregate inter-component edges between pairs of components. Since we only care about the total number of edges between two components, and their "type" (the parity c_e). But note that within a component, base coloring partitions the component's vertices into two sides (say side 0 and side 1 according to base). For any two components C and D, the edges of G between them can be classified by which side (base color) each endpoint is in. For a vertex u in C, base(u) is 0 or 1. So edges between C and D fall into four categories: from side 0 of C to side 0 of D, 0-1, 1-0, 1-1. For each such edge, the condition crossing = 1 if (x_C ⊕ x_D) = 1 ⊕ (b_u ⊕ b_v). If we denote b_u and b_v, then:
- If b_u=0, b_v=0 → c = 1⊕0⊕0 = 1. So crossing when x_C⊕x_D = 1.
- b_u=0, b_v=1 → c = 1⊕0⊕1 = 0 → crossing when x_C⊕x_D = 0.
- b_u=1, b_v=0 → c = 1⊕1⊕0 = 0 → crossing when x_C⊕x_D = 0.
- b_u=1, b_v=1 → c = 1⊕1⊕1 = 1 → crossing when x_C⊕x_D = 1.
So crossing condition: for edges connecting vertices with same base color (both 0 or both 1), crossing requires x_C and x_D to be different (since x_C⊕x_D = 1). For edges connecting vertices with different base colors, crossing requires x_C and x_D to be the same (x_C⊕x_D = 0). This is nice.
Thus, for each pair of components C and D, we have counts:
Let:
- a = number of edges from side0_C to side0_D + side1_C to side1_D (same base color edges). For these edges, crossing occurs if x_C != x_D.
- b = number of edges from side0_C to side1_D + side1_C to side0_D (different base color edges). For these edges, crossing occurs if x_C == x_D.
Let total edges between C and D be E_CD = a + b.
If we choose x_C and x_D, then crossing count from these edges is:
- If x_C == x_D: crossing = b (since for same base color edges, crossing requires different; but if same, those edges are not crossing, so crossing only from b). Actually check: if x_C == x_D, then x_C⊕x_D = 0. Then edges with c=1 (same base) would not be satisfied, while edges with c=0 (different base) would be satisfied. So crossing = b.
- If x_C != x_D: crossing = a.
So from perspective of maximizing total crossing, for each pair of components, the contribution depends on whether we assign them same or different flips.
Thus, we can aggregate across all component pairs. The overall objective (sum of crossing inter-component edges) can be expressed as: Sum over unordered pairs {C, D} of: if x_C == x_D then b_CD else a_CD.
Plus constant intra-component crossing edges (which we'll compute separately).
We want to choose x variables (binary for each component) to maximize total = constant + sum_{pairs} f_CD(x_C, x_D). This is like a graph partition problem: we have components, and between each pair we have two numbers a and b; we gain a if we put them in different groups, b if we put them in same group. But note that the groups are defined by the flip variable x (0 or 1). However, note that the flip variable assignment doesn't directly correspond to which side a vertex is ultimately assigned; but for inter-component edges, it's just about whether the flips are equal or not. So indeed we are partitioning the set of components into two sets (maybe empty) according to x value. This is a standard "maximum weight cut" style but with both same-set and different-set weights. Actually, we can transform: For each unordered pair (C, D), if we assign them to sets S0 and S1 based on x, then contribution =
- b_CD if both in same set,
- a_CD if in different sets.
Let’s denote we have a complete graph on components, but only some pairs have edges (there could be zero edges). For each pair, we have a_CD and b_CD. Usually, in partition problems, we can define a "gain" for putting two vertices together vs apart. But we can convert to maximizing a sum over edges of something.
Alternatively, we can think of flipping decisions: define sets X (x=0) and Y (x=1). Then total crossing from inter-component edges = sum_{C<D} [if same set -> b_CD; else a_CD].
Total = sum_{C<D} b_CD + sum_{C<D, different} (a_CD - b_CD). Because if they are different, we add a_CD instead of b_CD, so the change relative to baseline b_CD is (a_CD - b_CD). So total = const0 + sum_{C<D, different} (a_CD - b_CD), where const0 = sum_{C<D} b_CD (plus constant intra).
Thus maximizing total is equivalent to maximizing sum_{C<D, different} delta_CD where delta_CD = a_CD - b_CD. So we want to choose a partition of components into two sets to maximize the sum of delta over pairs that are across the cut. That's exactly a Max-Cut problem where edges have weights delta_CD (which can be positive, negative, zero). But note, this is "Max-Cut" but with the special condition that it's a complete graph potentially (but many deltas can be zero). However, Max-Cut is NP-hard in general, but here the number of components is up to 700, and the graph is arbitrary? But maybe the structure of delta_CD derived from the base coloring imposes some property that simplifies the problem? Let's examine.
We derived a_CD and b_CD from counts of edges between components based on the base coloring. This base coloring arises from the bipartite components of G'. Could that impose that the graph of components is bipartite? Not necessarily. Consider any two components, they may have edges in G, but we have no constraints linking them beyond that. So delta_CD can be arbitrary? Possibly. But maybe we can show that the graph of components is a "complete multipartite" something? Actually, the components are connected components of the complement graph G'. There is no particular structure between them. So delta_CD could be any integer between -E_CD and +E_CD. This seems like a general weighted Max-Cut instance, which is NP-hard. However, N is only 700, but solving Max-Cut exactly on a general graph with up to ~244k edges is NP-hard. However, perhaps there is a different perspective that avoids NP-hardness. Perhaps the problem is actually easier because G' is bipartite and we are maximizing crossing edges of G; maybe the solution corresponds to something like "maximum bipartite subgraph" or something. Let's double-check the problem statement: "Find the minimum possible number of roads whose endpoint cities belong to the same state." This is a known AtCoder problem? AtCoder often has problems that are solvable in polynomial time. N ≤ 700 suggests O(N^3) might be okay, but not NP-hard. So maybe we misinterpreted: The condition says "Any two cities in the same state, Taka or Hashi, are directly connected by a road." That means that within each group, the induced subgraph must be complete. This implies that the complement graph must be bipartite, as argued. However, the twist is that we are allowed to assign the cities arbitrarily, but we are not forced to use the bipartition induced by the complement graph's bipartite coloring? Wait, if the complement graph is bipartite, then any proper 2-coloring yields a valid partition. But if the complement graph is not bipartite, it's impossible. So that's correct.
But perhaps the problem is actually simpler: Because if we have a partition into two cliques, then the complement graph's edges are exactly those that go between the cliques. That means the complement graph is a complete bipartite graph? Not necessarily; it could have some missing edges between the two sets. But if the two sides are cliques, then in the complement, any edge inside either side is absent; edges between sides could be present or absent. So the complement graph is a subgraph of a complete bipartite graph. But it doesn't have to be complete bipartite. The condition for a partition into two cliques is exactly that the complement graph is bipartite. Because we need to color the vertices such that there are no edges inside same color in complement. That is exactly bipartiteness of the complement.
Thus we have a graph G' which we need to check bipartiteness. Then among all bipartitions (proper 2-colorings) we want to minimize internal edges. That's what we have.
Now the optimization: We need to find, among all proper 2-colorings of a bipartite graph, the one that maximizes crossing edges in G. This is essentially a "maximum cut respecting the constraints that all edges of G' must be crossing." But wait, that's different: In a proper coloring of G', all G' edges are crossing by definition. So G' edges impose constraints on the coloring. This is like a constraint satisfaction problem: we have to assign each node one of two colors such that for each edge in G', the colors differ. Then we want to maximize the number of edges in G that differ.
This is a classic "Max-Cut with side constraints" but the side constraints are that a set of edges (the G' edges) must be cut. That's equivalent to: we need to find a cut (partition) that contains all edges of G' (i.e., they are crossing) and maximizes the number of crossing edges in G. Since G' edges are a subset of all possible edges? Actually, G and G' are complements. So the complete graph on N vertices is partitioned into G (present) and G' (missing). So we have a set of edges that must be cut (G' edges). This is like: we have a graph with all possible edges (complete graph), each edge either has requirement "must be cut" (if it's in G') or "no requirement but we get benefit if cut" (if it's in G). And we need to find a bipartition (cut) that satisfies all must-cut edges (i.e., they are cut), and among those, maximize the number of G edges that are cut. This is a special case of the "minimum disagreement" or "correlation clustering" maybe? Actually, it's like we have a complete graph with each edge labeled either "similar" (must be in same side?) No.
Let's define: For each unordered pair (u,v), we have:
- If (u,v) is in G', then the condition demands col(u) != col(v). So it's a hard constraint that they be different.
- If (u,v) is in G, there's no constraint, but we get 1 point (or contribute to crossing) if col(u) != col(v), and we want to maximize sum of such points.
So this is exactly an instance of "Maximum Weighted 2-coloring with constraints" that can be solved via reduction to 2-SAT? But constraints are all of type "col(u) != col(v)" for G' edges, which are equality constraints? They are inequality constraints. This is similar to having a graph H = G' where we need to assign colors with all edges being bichromatic. That's exactly a 2-colorability (bipartite) problem. If H is bipartite, we have two possible assignments per connected component (up to flip). So the constraints fix relative colors within each component, but not the absolute colors across components. The objective is to maximize sum over all pairs (u,v) in G of indicator(col(u) != col(v)). Since G is the complement of H, G includes all pairs not in H.
Now this objective can be expressed in terms of component flips as earlier.
But maybe we can compute the maximum crossing edges efficiently via DP because the number of components might be small? But can it be as large as N=700? Possibly many isolated vertices if original graph is almost complete? But if original graph is almost complete, then G' is very sparse, thus many isolated vertices. In that case, we have many components of size 1, each of which can be colored arbitrarily independently. Then the problem reduces to: We have N vertices, each can be assigned color 0 or 1 independently, with no constraints (since if no G' edges, it's trivially bipartite). And we need to maximize the number of G edges crossing. That is exactly the Max-Cut problem on the original graph G. Max-Cut on a general graph is NP-hard, and N=700 is too large to solve exactly with exponential algorithms. But maybe the constraints (no constraints) is a special case that appears in the problem? Then the problem would be NP-hard, which contradicts it being an AtCoder problem (they don't give NP-hard problems without special constraints). So there must be a catch: When there are no constraints (G' empty), all colorings are valid, but we need to find the minimum internal edges. But that is equivalent to Max-Cut on G, which is NP-hard. However, perhaps we can do something else: When G' is empty, the condition "any two cities in same state are directly connected" means both sides must be cliques. That requires that G be complete? Wait, reexamine: If G' is empty, that means the original graph is complete. Actually, G' is the complement. If G' is empty, then G is the complete graph. In that case, any partition works? Because each side must be a clique; if G is complete, any subset is a clique. So yes, all partitions are valid. But then we want to minimize internal edges, i.e., edges inside each group. That's exactly minimizing the sum of edges inside groups. But in a complete graph, the number of internal edges for a given partition is C(|T|,2) + C(|H|,2). The total edges is C(N,2). So crossing edges = |T||H|. So we want to maximize |T||H|, which is maximized when groups are as balanced as possible (|T| ≈ N/2). So that is easy: we can compute that. So in this case, the problem reduces to a trivial balance problem, not general Max-Cut. Wait, but earlier I thought G' empty means no constraints; but also G is complete. So that's not general Max-Cut, because all possible edges exist. Indeed, if G is not complete, then G' is not empty. So the situation with many isolated vertices (size-1 components) arises when G' is sparse, but G is nearly complete. But then the constraints are still there: For each edge in G', we have to have opposite colors. If G' is sparse, it may not connect many vertices, so many vertices have no constraints relative to each other? Actually, if a vertex is isolated in G', that means it is connected to all other vertices in G? Since G' is complement, a vertex isolated in G' means it has all possible edges in G to every other vertex? Let's confirm: For a vertex v, if there is no G' edge incident to v, that means for every other u ≠ v, (v,u) is in G, because if it were missing, it would be in G'. So indeed, an isolated vertex in G' is adjacent to all other vertices in G. So the graph G is nearly complete: every vertex has high degree. In such a case, the constraints are very few (only those pairs that are non-edges in G). So the component structure of G' might be many isolated vertices and some small components. But is it possible that G' is sparse but still yields many components that are isolated? Yes. Then the optimization problem becomes: we have many vertices that are completely unrestricted relative to each other? However, note: For two isolated vertices u and v (i.e., no G' edges incident, and also no G' edge between them? Actually, if both are isolated, it means there is no G' edge between them (since G' edges are missing edges in G). Since they are isolated, there is no G' edge connecting them either. So (u,v) is in G. So there is an edge in G between them. But there is no constraint that they must be different or same. So they are free. So indeed we have a pair of vertices that can be colored arbitrarily; we want to decide whether to put them in same or different sides to maximize crossing edges. For that edge, crossing if they are different. So we get to choose to cut that edge or not. So that is exactly a binary decision variable per vertex. So the problem becomes: Given a graph G and a set of constraints that some pairs must be opposite (those in G'), choose colors to maximize number of edges in G that are cut. This is like "Max-Cut with a set of forced cuts". This is still NP-hard in general? Because if G' is empty, it's Max-Cut on G. But we saw that when G' is empty, G is complete, making Max-Cut trivial because the optimum is to balance sizes. However, if G is complete, Max-Cut is easy. But if G is arbitrary, can G' be empty? That only happens if G is complete, which is a special case. But what about if G is not complete? Then G' is not empty. The constraints might restrict the coloring enough to make the optimization tractable. But can it still be NP-hard? Possibly, but let's test: Suppose we take any instance of Max-Cut on a graph H. Could we encode it as an instance of this problem? We would need to construct G and G' such that G' constraints force certain relationships. Could we set G' to be empty? That would force G complete, so we cannot encode an arbitrary H. So maybe the constraints always force a certain structure that makes the problem polynomial.
Let's analyze the structure of G' (the complement) further. G' is bipartite. That imposes that the complement graph has no odd cycles. This is a strong condition on the original graph G: The complement graph is bipartite means that G is a "co-bipartite" graph? Actually, co-bipartite means complement is bipartite. So the condition is that G is co-bipartite. Indeed, the graphs that can be partitioned into two cliques are exactly the co-bipartite graphs. Because if G can be partitioned into two cliques, then its complement is a bipartite graph between those two cliques. Conversely, if complement is bipartite, then partition by its bipartition yields two cliques. So G must be a co-bipartite graph. The problem asks: Given a graph G, check if it is co-bipartite; if yes, among all possible bipartitions into two cliques (which correspond to bipartitions of complement), find the one minimizing internal edges. But note: Not every co-bipartite graph has a unique bipartition; there could be multiple ways to partition into two cliques because the complement bipartite graph may have multiple bipartitions (if it's disconnected). But still we need to choose the one that minimizes internal edges.
So the problem is: Given a co-bipartite graph G, find the bipartition of its vertex set into two cliques (i.e., a co-bipartition) that minimizes the number of edges inside the cliques (i.e., maximize edges across). This is essentially: maximize the number of edges between the two parts. Since G is co-bipartite, its complement is bipartite. Let's denote the complement bipartite graph H = G'. Suppose we fix a bipartition (X, Y) of the vertex set such that H has all edges only between X and Y (i.e., H is a subgraph of K_{X,Y}). Then G is the complement of H: So G contains all edges within X (since those are missing in H) and all edges within Y, and also edges between X and Y that are not in H. So G can be described as: start with two cliques (complete subgraphs on X and Y). Then add a set of cross edges (the complement of H) between X and Y, which are all possible cross edges except those present in H. So G is essentially two cliques plus some cross edges missing.
Now the condition for a bipartition into two cliques is that the chosen parts themselves must be cliques. In the representation above, if we choose parts (X, Y) as the two cliques, we need them to be cliques. Indeed, in the decomposition where H is bipartite with parts (U, V) (these are the two color classes from a proper 2-coloring of H). Then G has cliques on U and V (since all edges inside U are present in G because H has no edges inside U). Wait: H is bipartite with parts U and V, so H has no edges inside U or inside V. That means all edges inside U are missing from H, hence present in G. So U is a clique in G. Similarly V is a clique in G. So (U, V) is a valid bipartition into two cliques. But there may be other bipartitions: If H has multiple connected components, we can flip colors within each component, leading to a different partition (U', V') that also yields cliques? Let's check: In a component, flipping swaps some vertices from U to V and vice versa. After flipping, the new set U' is not necessarily a subset of the original U; but will the induced subgraph on U' be a clique? Suppose we take a component C of H that is bipartite with parts C0 and C1 (according to some base). In the original graph G, all edges inside C0 exist (since they are not in H) and all edges inside C1 exist. However, edges between C0 and C1 may or may not exist; actually, those edges are in H? Wait, H is exactly the set of missing edges in G. In a component C, edges between C0 and C1 are the edges of H (since H is bipartite between its color classes). So those edges are missing in G. But note: In G, the edges within C0 are present; within C1 are present; between C0 and C1 may be missing (if they are edges of H) but could also be present if they are not in H? Actually, by definition of H being the complement, for any u in C0, v in C1, the edge (u,v) is in G if and only if it is NOT in H. Since H is a bipartite graph with edges only between C0 and C1, but not necessarily all possible cross edges. So some cross edges may be present in G, some missing. That's fine.
Now, if we flip the colors in component C, we would reassign C0 to go to V and C1 to U (or vice versa). Then consider the new part U' (say all vertices assigned color 0 after flips). In the original G, does U' induce a clique? It may not, because there could be missing edges between vertices that were originally in different bipartition sets within the same component. Example: Suppose we have a component C with vertices a (in C0), b (in C1). The edge (a,b) is missing in G (since it's in H). If we flip so that a and b are both assigned to the same side (say both to U'), then within U' we have a pair (a,b) that is not an edge in G, violating the clique condition. Therefore, flipping within a component must preserve the property that each side is a clique. Wait, earlier we argued that any proper 2-coloring of H yields a partition into two cliques. Is that always true? Let's test: Given H is bipartite, a proper 2-coloring of H assigns colors such that each edge of H connects vertices of different colors. This ensures that no edge of H is inside a color class. That means that within each color class, there are no H-edges. But does that guarantee that within each color class, all G-edges exist? Since G is the complement of H, missing edges in G are exactly H edges. So if there is no H-edge inside a color class, then there are no missing edges inside that class, meaning that all pairs of vertices in the same class have an edge in G. So yes, that class is a clique. So any proper 2-coloring of H yields a partition into two cliques. But wait, does flipping within a component produce a proper 2-coloring of H? Yes, because if we flip all colors in a component, we still have a proper 2-coloring of H, because within that component, the bipartite structure is preserved: vertices that were originally opposite remain opposite after flipping? Actually, flipping changes each vertex's color to the opposite. Since the component is bipartite, if we have an edge (u,v) in H, originally we had col(u) != col(v). After flipping both, col'(u) = 1 - col(u), col'(v) = 1 - col(v), so they are still different because 1 - col(u) != 1 - col(v) if col(u) != col(v). So the new coloring is still proper. And for edges between components, the colors are independent; flipping one component doesn't affect edges between components because those edges are also in H? Actually, there are no H edges between different components? Wait, H may have edges between different components? By definition, components are maximal connected components in H. So there are no H edges between vertices in different components. So inter-component edges are not present in H. So there is no constraint linking colors of different components; they can be arbitrary. So any assignment of flips per component yields a proper coloring of H? Let's check: For an edge in H, its endpoints must be in the same component (since it's an edge). So flipping per component ensures that within each component, the properness is preserved. So yes, any combination of flipping decisions per component yields a proper 2-coloring of H. Conversely, any proper 2-coloring of H can be obtained from a base coloring by flipping some components, because within each component the coloring is uniquely determined up to flip. So indeed the set of valid partitions corresponds exactly to independent flipping of each connected component of H.
Thus my earlier derivation stands.
Now, about the optimization: It looked like a general Max-Cut on components with weights delta_CD. However, note that delta_CD = a_CD - b_CD. But recall that a_CD = number of edges between same-base-color pairs across components, b_CD = number of edges between different-base-color pairs. Since base coloring is derived from H's bipartition (the base assignment), we can think of the components as having two "parts" internally (the color classes). Edges between components in G can be classified. But maybe we can transform the problem into a min-cut or something using the fact that the complement is bipartite? Let's try to compute the crossing edges in terms of sizes.
Let’s denote for each component C, we have two groups: C0 (vertices with base color 0) and C1 (vertices with base color 1). These partition the vertices in C. In the base assignment (no flips), the two cliques are: Clique A = all vertices with color 0 (across all components) and Clique B = all vertices with color 1. That's a valid partition. In that assignment, the crossing edges in G are those edges between vertices of different colors (0-1). For edges inside same component, crossing occurs only for edges between C0 and C1? Wait, inside component, edges of G: There are edges within C0 (all present because no H edges), within C1 (all present), and between C0 and C1: some are missing (those that are H edges), some are present (those not in H). For the base coloring, color 0 vertices are in one side, color 1 in other. So an edge within component between C0 and C1 is crossing (since endpoints have different colors) if it exists in G. But note that edges between C0 and C1 that are in H are missing, so they don't count as crossing because they are not edges. So only present edges count. So intra-component crossing edges are exactly the number of G edges between C0 and C1. Similarly, edges within C0 are internal (both endpoints same color), so they are not crossing, they contribute to internal edges.
Now, when we flip a component, we swap the roles: C0 vertices become color 1, C1 become color 0. This changes which intra-component edges become crossing: After flip, edges within C0 (originally same color) become crossing? Actually, after flip, C0 vertices are now color 1, so edges within C0: both endpoints are color 1 => internal (not crossing). So intra-component edges within C0 and within C1 always remain internal, because they are always within the same side after any flip? Wait, careful: In the base assignment, C0 vertices are all color 0, so edges within C0 are internal. After flipping, C0 vertices become color 1, so edges within C0 are still internal because both are color 1. So indeed, edges within each base color class are always internal regardless of flip, because flipping toggles all vertices in the component simultaneously, so any two vertices that were originally in the same base class remain in the same class after flip? Actually, if we flip, C0 vertices all become color 1, but they all share the same new color, so they are still same color with each other. So edges within C0 remain same-colored. Similarly for C1. So intra-component edges that are inside either base class are always internal. Edges between C0 and C1: originally, these endpoints had different base colors, so in base assignment they are crossing. After flipping, C0 becomes color 1 and C1 becomes color 0, so they still have different colors (since swapped). So they remain crossing as well! Because they always have opposite base colors, and flipping both sides preserves opposite. So actually, for any component, the crossing status of an edge between two vertices within the same component is fixed: it is crossing if and only if the two vertices belong to different base classes AND the edge exists in G (i.e., it is not an H edge). But note: If the edge is missing (i.e., is in H), it's not counted anyway. So the contribution of intra-component edges is constant regardless of flips. Good.
Now, for inter-component edges: Consider vertices u in component C, v in component D. Their base colors are b_u (0/1) and b_v. After flips, colors become b_u XOR x_C, b_v XOR x_D. The crossing condition depends on x_C XOR x_D and the base colors. So that part is variable.
Thus, the problem reduces to: We have a set of components; each component C has two parts: size s_C^0 = |C0|, s_C^1 = |C1|. Also we have counts of edges between these parts across components. But maybe we can compute the objective in a more aggregated way. Let's denote for each component C, we can think of it as a "bipartite block" with two sides. When we choose the flip variable x_C, we are effectively deciding which side of component C aligns with global color 0 or 1. In other words, the global partition (T and H) will consist of: all vertices that end up with color 0, which come from some components' C0 (if x_C=0) or C1 (if x_C=1). So the two global groups are: Group A = ∪{C: x_C=0} C0 ∪ ∪{C: x_C=1} C1; Group B = complement.
Thus, the set of vertices in group A is: for each component, we take one of its two parts (depending on flip). So the partition is essentially: we select for each component which part goes to group A and which to group B. And we want to maximize the number of G edges between the two groups.
Now, G edges between different components are all present? Not all; G edges between components can be missing if they are in H? Wait, there are no H edges between different components because H edges only exist within a component (since components are maximal connected). Actually, H edges only exist within the same component? Yes, by definition of connected components, there are no edges in H connecting different components. So every pair of vertices from different components is not an edge in H. Therefore, for any u in component C, v in component D (C ≠ D), the pair (u,v) is NOT in H, which means it is present in G. Because G contains all pairs that are not in H. So all inter-component pairs are edges in G! This is a crucial observation.
Let's verify: H is the complement of G. So for any two distinct vertices u,v, either (u,v) is in G or in H. The components are defined in H. If u and v are in different components of H, that means there is no path in H connecting them. It does NOT necessarily mean that there is no direct edge in H between u and v. Actually, components are defined by connectivity via edges in H. It's possible that there is an H-edge directly between u and v even if they are in different components? No, if there is an H-edge between u and v, then they are directly connected, so they would be in the same component. So indeed, if u and v are in different components, there cannot be an H-edge between them. Therefore, for any u in C, v in D (C≠D), (u,v) is NOT an H edge, so it must be a G edge. So all inter-component pairs are present in G. Great!
This simplifies drastically: For any two distinct components, the original graph G contains all possible edges between any vertex in C and any vertex in D. So G is complete between components. So the only missing edges in G are those inside components that are in H (i.e., edges of H). So G is comprised of: For each component C, the induced subgraph on C is the complement of H[C] (which is a bipartite graph). And between components, it's complete.
Now, that's a big simplification. This means that for inter-component edges, we don't need to worry about whether the edge exists; it always exists. And we have full control over crossing via flips.
Thus, for each pair of distinct components C and D, all possible |C| * |D| edges are present in G. And we want to count how many of these edges become crossing based on assignment of flips. For a given assignment, the number of crossing edges between C and D equals: if we put the two components' chosen sides appropriately? Let's compute:
We have component C with two parts: C0 (size a_C = |C0|) and C1 (size b_C = |C1|). Under flip x_C, the vertices that go to group A (color 0) are: if x_C=0 then C0 goes to A, C1 to B; if x_C=1 then C1 goes to A, C0 to B. Similarly for D.
Now, crossing edges between C and D are edges that have one endpoint in A and one in B. So count = total edges between C and D minus edges inside the same group (both in A or both in B). But maybe easier: For fixed flips, we can compute crossing count as:
Let for component C, define p_C = number of vertices from C that are assigned to A; q_C = number assigned to B. Obviously p_C + q_C = |C|. Similarly for D. The number of edges between C and D that are crossing = p_C * q_D + q_C * p_D. Because edges from A-vertices in C to B-vertices in D, plus from B-vertices in C to A-vertices in D. And total edges between C and D = |C| * |D| = (p_C+q_C)*(p_D+q_D). So crossing = p_C * q_D + q_C * p_D.
But we can also compute this as: crossing = total - (edges both in A + both in B) = total - (p_C p_D + q_C q_D) = p_C q_D + q_C p_D. Yes.
Now, p_C depends on x_C: if x_C = 0, then p_C = |C0| and q_C = |C1|. If x_C = 1, then p_C = |C1|, q_C = |C0|.
Thus, for each component, we have two possible (p_C, q_C) pairs: either (a_C, b_C) or (b_C, a_C).
Now, the total crossing edges from inter-component pairs is sum over unordered pairs C<D of (p_C q_D + q_C p_D). Plus constant from intra-component edges (which are fixed, we'll add later).
We need to choose for each component which of the two (p_C,q_C) to use, to maximize total crossing.
This is a classic optimization problem: We have a set of items (components) each with two possible "vectors" (a_i, b_i). We want to choose orientation to maximize sum over i<j of (p_i q_j + q_i p_j). This is reminiscent of a quadratic objective. Let's denote total crossing = ∑{i<j} (p_i q_j + q_i p_j) = ∑{i<j} (p_i q_j + p_j q_i). This can be rewritten in terms of total sums. Let P = total number of vertices assigned to A (i.e., sum_i p_i). Let Q = total vertices assigned to B = N - P. Then what is ∑_{i<j} (p_i q_j + q_i p_j)? Let's compute:
∑_{i<j} (p_i q_j + q_i p_j) = ?
Consider expansion: ∑{i,j} p_i q_j for i≠j, but careful. ∑{i≠j} p_i q_j = (∑_i p_i)(∑j q_j) - ∑i p_i q_i. Since i and j range over components. But p_i q_i is internal to component i? Actually, p_i and q_i are numbers for same component, but we don't have edges within component considered in this sum? The sum is over i<j (different components), so i≠j. So ∑{i<j} (p_i q_j + q_i p_j) = (1/2) ∑{i≠j} (p_i q_j + q_i p_j). But maybe we can compute total crossing edges among inter-component pairs as: total crossing edges overall (including intra?) Actually we separate intra fixed. But overall, total edges crossing = crossing_inter + crossing_intra_fixed. But for now, just inter.
We have: ∑_{i≠j} p_i q_j = (∑_i p_i)(∑_j q_j) - ∑_i p_i q_i.
Similarly, ∑_{i≠j} q_i p_j = same thing, because it's symmetric. So sum of both = 2[(∑_i p_i)(∑_j q_j) - ∑i p_i q_i]. Then half of that for i<j gives: ∑{i<j} (p_i q_j + q_i p_j) = (∑_i p_i)(∑_j q_j) - ∑_i p_i q_i = P * Q - ∑_i p_i q_i.
Check: Because ∑{i<j} (p_i q_j + q_i p_j) = (1/2) ∑{i≠j} (p_i q_j + q_i p_j) = (1/2)[∑{i≠j} p_i q_j + ∑{i≠j} q_i p_j] = (1/2)[(P Q - ∑_i p_i q_i) + (P Q - ∑_i p_i q_i)] = P Q - ∑_i p_i q_i.
Yes. So total inter-component crossing edges = P * Q - ∑_{i} p_i q_i.
Where P = sum_i p_i, Q = N - P, and for each component i, p_i q_i is the product of the numbers of vertices from that component assigned to A and B. Note that p_i q_i = a_i b_i regardless of flip? Because if we assign p_i = a_i, q_i = b_i, then product = a_i b_i. If we flip, p_i = b_i, q_i = a_i, product = b_i a_i, same. So p_i q_i is invariant under flip! So ∑_i p_i q_i is constant across all valid assignments. Because for each component, product of sizes of the two parts is fixed (since flipping just swaps which part goes to A, but product same). So the term ∑_i p_i q_i is constant.
Thus, inter-component crossing edges = P * Q - constant, where constant = ∑_i a_i b_i (since each component contributes a_i b_i). So the only variable is P, the total number of vertices assigned to group A (or group 0). Because the constant is fixed, maximizing crossing_inter is equivalent to maximizing P * Q = P * (N - P). Since P*Q is maximized when P is as close as possible to N/2. So the inter-component crossing edges are maximized by making the total sizes of the two groups as balanced as possible.
But wait: Is P determined solely by the flips? Yes, because P = sum_i p_i, and each p_i is either a_i or b_i. So by choosing flips, we can adjust P within certain possible range. Specifically, for each component i, we can choose to contribute a_i or b_i to P. So we have a multiset of pairs (a_i, b_i). We need to select one value from each pair to sum to P. The possible P values are all sums achievable by picking from each component either a_i or b_i. And we want to choose a combination (i.e., assignment of flips) that makes P as close as possible to N/2 (to maximize P*(N-P)), while also ensuring that the assignment corresponds to a valid coloring (but all assignments are valid). So the problem reduces to: Given a list of numbers a_i, b_i (with a_i + b_i = size of component i), we need to select either a_i or b_i for each component to make total sum S, and we want to maximize S*(N-S). Since S*(N-S) is symmetric and increases as S approaches N/2, we want S to be as close to N/2 as possible. So we need to find an achievable sum S (by picking one from each pair) that is closest to N/2. Then max crossing_inter = S*(N-S) - ∑ a_i b_i. Then total crossing = crossing_inter + crossing_intra_fixed. Then answer = M - total_crossing.
But is that all? Let's double-check: Did we account for all inter-component edges correctly? We used the fact that all inter-component edges are present. Yes, because if two vertices are in different components of H, there is no H edge between them, so they are in G. So indeed the graph between components is complete.
Now, what about edges within the same component? Those are not complete; they are exactly the complement of H within the component. But as argued, their crossing status is constant regardless of flips. So crossing_intra_fixed can be computed from the base assignment (or any). So total crossing = constant_intra_cross + (P*Q - ∑ a_i b_i). And constant_intra_cross = sum over components of the number of G edges that are between the two base color classes (i.e., edges that are present in G and connect C0 and C1). Because these are crossing in any coloring. Let's confirm: In any coloring, the crossing status of an edge between two vertices