Road Signs#3081
Different countries use different background colors for road direction signs. For example, in Rudolandia, road signs in urban areas have white backgrounds, signs in the countryside have blue backgrounds, and signs on motorways have green backgrounds.
The king of Flatland once got lost while traveling around the country, which inspired him to introduce a new rule for the background colors of road signs on motorways. In Flatland, there are cities connected by bidirectional motorways. There are at most motorways incident to any city. According to the king's plan, the signs on the motorways will have one of d+1 background colors. The rule is that no two motorways incident to the same city may have the same background color on their signs. After the reform, whenever you see a sign on a motorway, you need only remember the city you departed from to immediately understand which city you are headed to (assuming perfect memory).
Given the plan of motorways in Flatland, help the king decide which background color should be assigned to each motorway.
The first line of the input file contains three integers , , and (2 \leq n \leq 200, 1 \leq m \leq 2000, 1 \leq d \leq n-1). The following lines describe the motorways. Each motorway is described by two integer numbers from to — the numbers of the cities it connects. No city has more than motorways incident to it.
If it is impossible to assign the colors from to d+1 to the motorways so that no two motorways incident to the same city have the same color, output on the first line of the output file.
Otherwise, output integers from to d+1 — the colors to be assigned to the motorways (in the order the motorways are described in the input file).
Esempio 1