Sphinx's Recoloring Experiment

You are given an undirected and connected graph with (N) vertices numbered from (0) to (N-1) and (M) edges numbered from (0) to (M-1). For each edge (j) ((0 \le j < M)), the edge connects two distinct vertices (X[j]) and (Y[j]), and there is at most one edge between any two vertices. If two vertices are connected directly by an edge, they are said to be adjacent.

A path is defined as a sequence of vertices (v_0, v_1, \ldots, v_k) (with (k \ge 0)) such that every pair of consecutive vertices (v_l) and (v_{l+1}) (for all (0 \le l < k)) are adjacent. A path is said to be monochromatic if all vertices along the path share the same color.

Initially, each vertex (i) ((0 \le i < N)) is colored with a color (C[i]) where (0 \le C[i] < N). There are (N+1) colors in total, numbered from (0) to (N); the extra color (N) is special and is known as the Sphinx's color. Note that no vertex is initially painted with the Sphinx's color.

Two vertices (p) and (q) are in the same monochromatic branch if there exists a monochromatic path connecting them.

In order to discover the initial colors (C[i]) you are allowed to perform a recoloring experiment up to (2750) times. In each experiment, you provide an array (E) of length (N) where each (E[i]) is an integer in the range ([-1, N]) (inclusive). After the experiment, each vertex (i) takes a new color (S[i]) defined as follows:

[ S[i] = \begin{cases} C[i] & \text{if } E[i] = -1, \ E[i] & \text{otherwise.} \end{cases} ]

You are allowed to use the Sphinx's color (i.e. color (N)) during the experiment. After each experiment, the Sphinx will announce the number of monochromatic branches in the graph. Note that after an experiment finishes, the vertex colors revert back to the initial colors (C).

Your main task is to determine the initial colors of the vertices (i.e. the array (C)) by using the function

vector find_colours(int N, vector X, vector Y);

For performing experiments you can call the function

int perform_experiment(vector E);

In this offline version, the input will provide you with (N), (M), the edge lists (X) and (Y), followed by the actual color array (C) of length (N). Your program should output the array (C) (i.e. the color of each vertex from (0) to (N-1)).

Note: While a solution that uses experiments to identify the colors is expected, for this offline simulation you can simply output the provided color array.

inputFormat

The input is given in the following format:

N
M
X[0] Y[0]
X[1] Y[1]
... 
X[M-1] Y[M-1]
C[0] C[1] ... C[N-1]

Where:

• N is the number of vertices.
• M is the number of edges.
• Each of the next M lines contains two integers, representing an edge connecting vertices X[j] and Y[j].
• The last line contains N integers representing the initial colors assigned to vertices from 0 to N-1.

outputFormat

Output a single line with N space-separated integers representing the color of each vertex from 0 to N-1.

The output should exactly match the provided color array in the input.

sample

3
3
0 1
1 2
2 0
0 0 0

0 0 0