(20 points)
Write a program to color the countries of a map.
A map contains n countries, and we want to determine whether it is possible to use c colors so that no two adjacent countries share the same color.
Each country has a unique ID from 1 to n, and each color has a unique ID from 1 to c.
Line 1: Three integers
n c p
where
n = number of countries
c = number of available colors
p = number of adjacent country pairs
Next p lines: Each line contains two integers
i j
meaning that country i and country j are adjacent and therefore cannot have the same color.
If a valid coloring exists, output n integers, separated by spaces.
The k-th integer represents the assigned color of country k.
Among all possible valid colorings, output the lexicographically smallest sequence.
If no valid coloring exists, output:
no solution