Write a program to color the countries on a map.
Given a map with n countries, determine whether it is possible to color these countries using c colors so that no two adjacent countries have the same color.
Each country is assigned a unique ID from 1 to n, and each color is assigned a unique ID from 1 to c.
Constraints:
0 < n ≤ 20, 0 < c ≤ 6, 0 < p ≤ 400
The first line of input contains the number of countries n, the number of colors c, and the number of pairs of adjacent countries p.
The following p lines each contain two country IDs representing a pair of neighboring countries.
Ex. 5 3 7
0 1
0 4
1 2
1 3
1 4
2 3
3 4
If a valid coloring exists, output the color ID assigned to each of the n countries in order.
Since multiple symmetric solutions may exist, output the one that is lexicographically smallest when viewed as a string.
If no solution exists, output "no solution".
Ex. 1 2 3 1 3