Problem G
Gotta Trade Some of 'Em

Two Game Boy systems connected with a DMG-04 (link cable). Public domain photo by KoS.

The kids at school are obsessed with a new video game of collectible pocket monsters called Pokémon. Their goal is to “catch ’em all” by completing the Pokédex, meaning they want to catch a copy of every Pokémon. Typically they do this by playing the game, encountering Pokémon, and catching them with a Pokéball.

Pokémon games are released in different variants. Each variant contains a number of Pokémon, some of which are exclusive to that variant. For example, only Pokémon Blue (variant $1$) allows encounters with the Pokémon known as Meowth. Thus, a kid owning Pokémon Red (variant $2$) cannot catch Meowth, and therefore must trade with a friend who has a Meowth to fill the Pokédex. This friend may either own Pokémon Blue or have received Meowth through another trade.

Your task is to distribute Pokémon variants to the kids so that, through trading among friends, every kid can eventually collect at least one of each Pokémon. Each kid receives exactly one Pokémon game variant. Each variant comes with enough copies of its Pokémon, both its exclusives and the non-exclusives, ensuring trades are always possible.

Input

The input consists of:

• One line with three integers $n$, $m$, and $k$: the number $n$ of kids, with $1 \leq n \leq 100\, 000$, the number $m$ of friendships, with $1 \leq m \leq 200\, 000$, and the number $k$ of different game variants, with $1 \leq k \leq 100\, 000$.

• $m$ lines, each containing two integers $a$ and $b$ with $1\leq a < b \leq n$, representing that $a$ and $b$ are friends.

Output

Ouput $n$ integers, one for each kid, representing which game variant that kid should get. Your output will be considered correct if all kids can fill their Pokédex by using any number of trades with their friends.

If there are multiple valid solutions, you may output any one of them.

If there is no assignment of game variants to kids that allows all kids to fill their Pokédex, output impossible.

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

1 2 1 2 1 2 1 2

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

impossible

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

1 2 3 4 5 6 7 8