A game has $n$ planets, connected by $m$ teleporters. Two planets $a$ and $b$ belong to the same kingdom exactly when there is a route both from $a$ to $b$ and from $b$ to $a$ . Your task is to determine for each planet its kingdom.
The first input line has two integers $n$ and $m$ : the number of planets and teleporters. The planets are numbered $1,2,\dots,n$ .
After this, there are $m$ lines describing the teleporters. Each line has two integers $a$ and $b$ : you can travel from planet $a$ to planet $b$ through a teleporter.
First print an integer $k$ : the number of kingdoms. After this, print for each planet a kingdom label between $1$ and $k$ . You can print any valid solution.
5 6 1 2 2 3 3 1 3 4 4 5 5 4· \n · \n · \n · \n · \n · \n · \n
2 1 1 1 2 2\n · · · · \n