Galaxy Interconnection#2376
More than years have passed since the first ACM ICPC. Several civilizations of our Galaxy, including Earth, are united in the Great Circle, whose members exchange scientific and cultural information. Due to the distribution of gravity and dark energy flows in the galaxy, there are bidirectional communication channels between some planets. Through these channels, civilizations can share knowledge across the entire Great Circle.
Now it is time to distribute research among the civilizations: each planet must choose one of main research areas (such as Repagular Calculus or Given String Theory).
The choice of was not accidental. The Great Circle began with the Initial Circle — a set of planets connected by channels forming a cycle. Later, new channels were explored and constructed, and new planets joined the Great Circle. However, due to the high energy cost of communication channels, each planet in the Great Circle has strictly fewer than channels.
Two planets connected by a direct channel must not choose the same research area: it is better if they choose different areas and share their research results.
There is one more limitation. Periodically, civilizations send space expeditions to explore new planets and visit neighbors in the Great Circle. Expeditions are planned so that spaceships can travel from one planet to another if those planets are connected by a communication channel. This aids in preparing the expeditions: building refueling stations, optimizing ship communication systems, and so on.
Some expeditions, called Research Audits, are planned in such a way that a spaceship starts from a planet, then makes k - 1 jumps, visiting a total of planets (including the starting planet). These planets together must provide all research areas: the expedition will check the progress of research.
Your task is to choose a research area for each planet so that: - No two planets connected by a communication channel have the same research area; - It is possible to start a Research Audit expedition from every planet of the Great Circle.
The first line of the input contains three integers: , , and — the number of planets in the Great Circle, the number of research areas, and the number of communication channels (3 \le n \le 5000; 3 \le k \le \min(n, 10); 1 \le m \le 10000).
The next lines describe the channels, one per line. Each communication channel is described by two integers — the identifiers of the planets it connects. Planets are numbered from to , such that the planets numbered from to form the Initial Cycle.
Output exactly integers in one line. The -th integer should denote the research area for planet (an integer from to ).
Example 1