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.
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, fi, the frequency assigned to temple i, where 1 ≤ fi ≤ K. If there is more than one solution, any one will do.
## Input
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·104 0 ≤ M ≤ 5·105 1 ≤ K ≤ N 1 ≤ fi ≤ K
## Output
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, fi, the frequency assigned to temple i, where 1 ≤ fi ≤ K. If there is more than one solution, any one will do.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ N_k \in \mathbb{Z} $ be the number of channels.
- Let $ C_k = \{(S_{k,i}, F_{k,i}) \mid i \in \{1, \dots, N_k\}\} $ be the set of channel-frequency pairs, where:
- $ S_{k,i} \in \Sigma^* $ is a non-empty string of lowercase English letters ($|\Sigma| \leq 50$),
- $ F_{k,i} \in \mathbb{Z} $ is the frequency ($11111 \leq F_{k,i} \leq 99999$).
**Constraints**
1. $ 1 \leq T \leq 100 $
2. For each $ k \in \{1, \dots, T\} $:
- $ 1 \leq N_k \leq 10^4 $
- $ 11111 \leq F_{k,i} \leq 99999 $ for all $ i \in \{1, \dots, N_k\} $
**Objective**
For each test case $ k $, find the frequency $ f^*_k $ that maximizes the count of channels with that frequency.
If multiple frequencies achieve the maximum count, choose the smallest such frequency:
$$
f^*_k = \arg\min_{f \in \text{Freq}_k} \left\{ f \,\middle|\, \max_{f' \in \text{Freq}_k} \left| \left\{ i \in \{1, \dots, N_k\} \mid F_{k,i} = f' \right\} \right| \right\}
$$
where $ \text{Freq}_k = \{ F_{k,i} \mid i \in \{1, \dots, N_k\} \} $.