Different countries use different background color for road direction signs. For example, in Russia road signs in urban areas have white background, signs in the country have blue background, signs on motorways have green background. In Europe motorways signs sometimes have blue background, in USA most signs have green background. The king of Flatland once got lost when traveling around the country, and that made him come up with an idea. He is planning to introduce a new rule for background colors of road signs on motorways. There are \textbf{n} cities in Flatland, connected by \textbf{m} bidirectional motorways. There are at most \textbf{d} motorways incident to any city. Following the king's plan the signs on the motorways will have one of \textbf{d+1} background colors. The rule is that no two motorways incident to the same city have the same background color for signs. After the reform whenever you see a sign on a motorway you must only remember the city you departed from, and you immediately understand what city you are going to (at least if you have perfect memory). Given the plan of motorways in Flatland, help the king to decide which motorway would have which sign background color. \InputFile The first line of the input file contains three integer numbers \textbf{n}, \textbf{m} and \textbf{d} (\textbf{2} ≤ \textbf{n} ≤ \textbf{200}, \textbf{1} ≤ \textbf{m} ≤ \textbf{2000}, \textbf{1} ≤ \textbf{d} ≤ \textbf{n-1}). The following \textbf{m} lines describe motorways, each motorway is described by two integer numbers ranging from \textbf{1} to \textbf{n} - the numbers of cities it connects. No city has more than \textbf{d} motorways incident to it. \OutputFile If it is impossible to assign colors from \textbf{1} to \textbf{d+1} to motorways so that no two motorways incident to the same city were assigned the same color, output \textbf{-1} at the first line of the output file. In the other case output \textbf{m} integer numbers ranging from \textbf{1} to \textbf{d+1} - the colors that must be assigned to motorways (in order the motorways are described in the input file).