DColorare

Cerință

Se dă un graf neorientat cu $N$ noduri și $M$ muchii. Se cunoaște că gradul fiecărui nod este $\leq D$. Să se coloreze nodurile grafului în cel mult $D + 1$ culori astfel încât oricare două noduri vecine să nu aibă aceeași culoare.

Date de intrare

Pe prima linie se găsesc numerele naturale $N$, $M$ și $D$. Pe următoarele $M$ linii se găsesc câte două numere naturale $x$ și $y$ reprezentând muchiile grafului.

Date de ieșire

Programul va afișa pe ecran $N$ numere naturale cuprinse în intervalul $[1, D + 1]$, al $i$-lea număr reprezentând culoarea nodului $i$.

Restricții și precizări

• $1 \leq N, M, D \leq 10^5$
• Pot exista mai multe soluții, se acceptă oricare.

Exemple

Intrare

10 10 3
7 10
1 5
2 5
2 4
2 6
6 9
4 8
8 9
3 10
5 7

Ieșire

1 1 1 2 2 2 1 1 3 2