1785. The Biggest Group a Split Can Give

An UNDIRECTED graph has n vertices and m edges. Split ALL the vertices into exactly two groups so that no edge joins two vertices in the same group. A group is allowed to be empty.

Among all such splits, print the size of the LARGEST group, maximised over the splits. Print -1 if no split exists.

1-2, 2-3 -> 2 {1,3} and {2} 1-2, 3-4 -> 2 {1,3} and {2,4}, choosing per piece star: 1-2, 1-3, 1-4 -> 3 {2,3,4} and {1} no edges, n = 5 -> 5 everything in one group 1-2, 2-3, 3-1 -> -1

## This is NOT the largest set with no edge inside it

Those two questions have different answers, and the difference is the whole point of having this problem next to the matching problems later in this topic.

vertices 1, 2, 3, 4, 5, 6 edges 1-4, 2-4, 3-4, 1-5, 1-6

Every split of that graph forces vertex 1 and vertex 4 into different groups, vertices 2 and 3 into vertex 1's group, and vertices 5 and 6 into vertex 4's group. So the only splits are {1,2,3} with {4,5,6} and the mirror image, and the largest group in any split is 3.

But {2, 3, 5, 6} has FOUR vertices and no edge inside it, since the only edges listed touch vertex 1 or vertex 4. It is not a group of any split, because a split has to place vertices 1 and 4 somewhere too, and wherever they go one of them lands beside a neighbour. That set of four is a declared test here.

So "split everything in two and take the bigger half" is strictly weaker than "find the biggest edge-free set", and the second question needs a matching argument rather than a colouring. This problem asks the first one.

## What most people try first

Taking the larger of the two groups the colouring happened to produce. That is right for a connected graph and wrong as soon as there are two pieces, because each piece can be flipped independently and the big group should collect the bigger side of EVERY piece.

``` n = 6, edges 1-2, 1-3, 5-4, 5-6

piece {1,2,3}: 1 alone on one side, 2 and 3 on the other piece {4,5,6}: 5 alone on one side, 4 and 6 on the other

a colouring that starts each piece from its smallest vertex: side A = {1, 4, 6}, side B = {2, 3, 5} larger group 3

flipping the second piece: side A = {1, 5}, side B = {2, 3, 4, 6} larger group 4 ```

So the colouring's own two sides give 3 and the answer is 4. The gap grows with the number of pieces, and which way a piece happens to be coloured is decided by nothing more interesting than which of its vertices carries the smallest number.

## The method

if no split exists: -1 otherwise: for each connected piece, work out the sizes a and b of its two forced sides answer = sum of max(a, b) over the pieces

## Why it is correct

Within a piece there are exactly two splits, because fixing one vertex's group forces every other by the parity of its distance, which problem 1784 argues in full. So a piece contributes either a to the first group and b to the second, or the other way round.

Pieces have no edges between them, so their two-way choices are completely independent: any combination of per-piece flips is a legal split of the whole graph. To make the first group as big as possible, give it the bigger side of every piece, which is achievable precisely because the choices are independent. That yields sum of max(a, b).

And it is the largest group of that split, because sum of max(a, b) is at least sum of min(a, b), so the group being maximised really is the larger of the two. No other split can beat it, since the first group's size is a sum of one side per piece and each term is at most max(a, b).

## The boundaries that break a careless implementation

A vertex with NO EDGES is a piece whose sides are 1 and 0, and max(1, 0) = 1, so it joins the big group. Skipping edge-free vertices because they look irrelevant loses one per vertex, and n = 200000 with m = 0 then prints 0 instead of 200000.

A SELF-LOOP makes the answer -1, since its two ends are one vertex.

m = 0 gives n.

A piece of a single edge has sides 1 and 1, so max is 1 and the two endpoints genuinely cannot both be in the big group.

## Cost

O(n + m): one iterative search per piece, counting both sides as it goes. The search must be iterative because a path-shaped graph of 200000 vertices overflows Python's recursion limit of 1000 and the default stack elsewhere.

## Overflow

The answer is at most n, which is 200000, and the running sum is bounded by the same. Nothing comes near the 32-bit signed limit of 2147483647.

## Worked example

edges: 1-2, 1-3, 1-4, 5-6 pieces: {1,2,3,4} sides {1} and {2,3,4} -> max 3 {5,6} sides {5} and {6} -> max 1 answer: 4 split: {2,3,4,6} and {1,5}

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - a self-loop can occur and makes the answer `-1` - repeated edges can occur and change nothing - the graph may be disconnected, and each piece can be flipped independently of the others - a group may be empty, which is what happens when `m` is 0