1782. Print the Split, Not Just Whether It Exists

An UNDIRECTED graph has n vertices and m edges. Split the vertices into two groups, numbered 1 and 2, so that no edge joins two vertices in the same group, and print the group of every vertex. If no such split exists, print NO.

The split is NOT unique, so the statement pins exactly one of them:

> In each connected piece of the graph, the vertex with the SMALLEST number > takes group 1.

That one sentence settles everything, because once one vertex in a piece has its group, every other vertex in that piece is forced: a neighbour must be in the other group, a neighbour of a neighbour back in the first, and so on. A vertex with no edges is a piece by itself, is its own smallest vertex, and so takes group 1.

1-2, 2-3, 3-4 -> YES 1212 1-2, 2-3, 3-1 -> NO 1-2, 3-4 -> YES 1212 two pieces, vertex 1 and vertex 3 each start no edges, n=3 -> YES 111 three pieces of one vertex each 1-1 -> NO both ends of a self-loop are one vertex

Problem 366 answers Yes or No to the same question. This one prints the split, which is why the tie-break above has to exist at all, and it also allows self-loops and repeated edges, which problem 366 rules out.

## What most people try first

Colouring from vertex 1 only. That leaves every other piece uncoloured, and a graph is allowed to be disconnected here, so the loop has to restart at every vertex that has not been reached yet. The second common error is to pick an arbitrary starting vertex per piece, which gives a legal split but not the one asked for: every vertex of the piece is then possibly swapped.

## The method

for s = 1, 2, ..., n: if s already has a group, skip it give s group 1 and search outward from s, giving each newly reached vertex the opposite group to the vertex it was reached from if an edge is ever found between two vertices already in the same group, the whole answer is NO

Because the outer loop runs in increasing order of s, the vertex that starts a piece is automatically that piece's smallest, with no extra bookkeeping.

## Why the answer is forced, and so unique

Pick a piece and its smallest vertex r. Every vertex v in that piece has some walk from r. Along a walk the group must alternate, so v's group is decided by whether the walk has even or odd length. Two different walks from r to v must therefore agree on that parity, or the two walks joined together make a closed walk of odd length, and a closed walk of odd length contains an edge inside a group somewhere. So on a graph that can be split at all, parity from r is well defined, and it fixes every group in the piece once r is group 1.

That also shows the search order cannot matter: the answer depends only on the parity of the distance from r, and not on which neighbour was visited first.

## The boundary that breaks a careless implementation

A SELF-LOOP is an immediate NO. Its two ends are the same vertex, which cannot be in two groups at once. An implementation that skips an edge when both ends are already coloured the same, instead of failing, will quietly report YES.

A REPEATED EDGE changes nothing at all and must not be treated as a conflict. Seeing 1-2 twice is still the one constraint that 1 and 2 differ.

m = 0 is YES with every vertex in group 1, since every vertex is its own piece.

## Cost

O(n + m): each vertex is reached once and each edge is inspected twice, once from each end. The search has to be ITERATIVE, with an explicit queue or stack, because n reaches 200000 and a path-shaped graph of that length overflows Python's recursion limit of 1000 and the default stack in C, C++ and Java.

## Worked example

``` edges: 1-2, 2-3, 3-4, 5-6 pieces: {1,2,3,4} and {5,6}

piece from 1: 1 -> group 1 2 is a neighbour of 1 -> group 2 3 is a neighbour of 2 -> group 1 4 is a neighbour of 3 -> group 2 piece from 5: 5 -> group 1, 6 -> group 2

output: YES 121212 ```

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - a self-loop can occur and makes the answer `NO` immediately, because its two ends are one vertex - repeated edges can occur and change nothing - the graph may be disconnected, and a vertex with no edges is a piece of its own and takes group 1