Consider an undirected graph G = (V,E), in which each node u 2 V may be colored

with some color between 1 and C. task is provide program that determine the colors

for the uncolored nodes in the graph such that

For all edges (u, v) 2 E, u and v have different colors.

The number of additional colors needed is minimum.

Input (Standard input): Includes multiples lines. The first line contains two integers

1 n 1000, 1 m 100000 that correspond to the number of nodes and edges,

respectively.

Each of the following m lines contain two integers u and v, separated by one space,

to denote an edge from u to v. Nodes are numbered from 1 to n.

The last line contains n integers that are the colors of the nodes. Uncolored nodes

are indicated with color 0.

Output (Standard output): The first line contains an integer 0 D n that is the

number of additional colors needed to color all the uncolored nodes in the graph.

The next line contains n positive integers that are colors of the nodes.

Input ---------- Output

9 18 -------------1

1 2 ---------------1 2 3 2 3 1 3 1 2

1 3

1 4

1 7

2 3

2 5

2 8

3 6

3 9

4 5

4 6

4 7

5 6

5 8

6 9

7 8

7 9

8 9

0 2 0 2 0 1 0 1 0----------

write program in Java/C++ that solves the above problem following the above input/

output format. A makefile and/or compiling instruction should be included if

you have multiple source files. Your program should not take more than 2 minutes to

terminate on any graph within the limits described in the Input section.