404384: GYM101492 A Comunicating the Tibet

The Himalayas form the highest mountain range in the world (with mountains as high as 7,200 meters). Located in Asia, this mountain system has parts in the Bhutan, China, India, Nepal, and Pakistan. In China, the Tibet is a region delimited by the Himalayas.

The Tibet, which is the highest region on Earth, is an autonomous region inside the People's Republic of China. In this region there are Buddhist temples with Tibetan monks, which are visited every year by many people from the whole world. To facilitate communication, the Central Tibetan Administration (ACT, in Portuguese) wishes to install some radio-frequency antennas around the Tibet. The ACT considered the N most important temples where they wish to install these antennas. The World Communication Association (ACM, in Portuguese) was hired to setup and configure these antennas at the temples. ACM charged their star engineer Mashiro "thunderstorm" Sanae with this job.

After reading about the history and customs of Tibetan monks, Mashiro found a curious fact: the Tibetans have a particular fixation for the number K. By studying the map with the location of the N temples, Mashiro noticed that if he walks through distinct temples until he returns to the starting one, the number of temples he goes through (including the first) never has the form mK + 1 for any nonnegative integer m. He was fascinated with his discovery, and realized the importance of the number K for Tibetans. Mashiro knows that, when setting up the antennas, neighboring temples should receive distinct frequencies to avoid interference. Having this constraint in mind and knowing the importance of the number K for the Tibetans, Mashiro wishes to find an assignment of frequencies to antennas that uses at most K distinct frequencies, or determine that this assignment is impossible.

Mashiro had an idea to solve this problem and has already started coding it. Can you beat him to it?

The first line has three integers, N, M, and K, the number of temples, the number of paths that join neighboring temples and the special number revered by the Tibetan people, respectively. The temples are represented by numbers from 1 to N.

The next M lines contain two distinct integers each. Each pair of integers represents two neighboring temples. No two lines among these M lines contain the same pair of integers.

• 1 ≤ N ≤ 5·10⁴
• 0 ≤ M ≤ 5·10⁵
• 1 ≤ K ≤ N
• 1 ≤ f_i ≤ K

If there is no possible frequency assignment to the temples, print a line containing "-1" (without the double quotes). Otherwise, print N lines. The i-th line must contain a single integer, f_i, the frequency assigned to temple i, where 1 ≤ f_i ≤ K. If there is more than one solution, any one will do.

4 0 1

1
1
1
1

3 3 3
1 2
2 3
1 3

1
2
3

3 2 1
1 2
2 3

-1