Sphinx's Riddle

문제

The Great Sphinx has a riddle for you. You are given a graph on $NN$ vertices. The vertices are numbered from $00$ to $N-1N\; -\; 1$. There are $MM$ edges in the graph, numbered from $00$ to $M-1M\; -\; 1$. Each edge connects a pair of distinct vertices and is bidirectional. Specifically, for each $jj$ from $00$ to $M-1M\; -\; 1$ (inclusive) edge $jj$ connects vertices $X[j]X[j]$ and $Y[j]Y\; [j]$. There is at most one edge connecting any pair of vertices. Two vertices are called adjacent if they are connected by an edge.

A sequence of vertices $v_0,v_1,\dots ,v_{k}v\_0\; ,\; v\_1\; ,\; \backslash dots\; ,\; v\_k$ (for k &ge; 0) is called a path if each two consecutive vertices $v_{l}v\_l$ and $v_{l+1}v\_\{l+1\}$ (for each $ll$ such that 0 &le; l < k) are adjacent. We say that a path $v_0,v_1,\dots ,v_{k}v\_0\; ,\; v\_1\; ,\; \backslash dots\; ,\; v\_k$ connects vertices $v_{0}v\_0$ and $v_{k}v\_k$. In the graph given to you, each pair of vertices is connected by some path.

There are $N+1N\; +\; 1$ colours, numbered from $00$ to $NN$. Colour $NN$ is special and is called the Sphinx's colour. Each vertex is assigned a colour. Specifically, vertex $ii$ (0 &le; i < N) has colour $C[i]C[i]$. Multiple vertices may have the same colour, and there might be colours not assigned to any vertex. No vertex has the Sphinx's colour, that is, 0 &le; C[i] < N (0 &le; i < N).

A path $v_0,v_1,\dots ,v_{k}v\_0\; ,\; v\_1\; ,\; \backslash dots\; ,\; v\_k$ (for k &ge; 0) is called monochromatic if all of its vertices have the same colour, i.e. $C[v_l]=C[v_{l+1}]C[v\_l\; ]\; =\; C[v\_\{l+1\}\; ]$ (for each $ll$ such that 0 &le; l < k). Additionally, we say that vertices $pp$ and $qq$ (0 &le; p < N, 0 &le; q < N) are in the same monochromatic component if and only if they are connected by a monochromatic path.

You know the vertices and edges, but you do not know which colour each vertex has. You want to find out the colours of the vertices, by performing recolouring experiments.

In a recolouring experiment, you may recolour arbitrarily many vertices. Specifically, to perform a recolouring experiment you first choose an array $EE$ of size $NN$, where for each $ii$ (0 &le; i < N), $E[i]E[i]$ is between $-1-1$ and $NN$ inclusive. Then, the colour of each vertex $ii$ becomes $S[i]S[i]$, where the value of $S[i]S[i]$ is:

• $C[i]C[i]$, that is, the original colour of $ii$, if $E[i]=-1E[i]\; =\; -1$, or
• $E[i]E[i]$, otherwise.

Note that this means that you can use the Sphinx's colour in your recolouring.

Finally, the Great Sphinx announces the number of monochromatic components in the graph, after setting the colour of each vertex $ii$ to $S[i]S[i]$ (0 &le; i < N). The new colouring is applied only for this particular recolouring experiment, so the colours of all vertices return to the original ones after the experiment finishes.

Your task is to identify the colours of the vertices in the graph by performing at most $27502\backslash ,\; 750$ recolouring experiments. You may also receive a partial score if you correctly determine for every pair of adjacent vertices, whether they have the same colour.