A13816 | BubbleSquare Tokens

BubbleSquare social network is celebrating $13^{th}$ anniversary and it is rewarding its members with special edition BubbleSquare tokens. Every member receives one personal token. Also, two additional tokens are awarded to each member for every friend they have on the network. Yet, there is a twist – everyone should end up with different number of tokens from all their friends. Each member may return one received token. Also, each two friends may agree to each return one or two tokens they have obtained on behalf of their friendship.

First line of input contains two integer numbers $n$ and $k$ ( $2$ $\leq$ $n$ $\leq$ $12500$ , $1$ $\leq$ $k$ $\leq$ $1000000$ ) - number of members in network and number of friendships.

Next $k$ lines contain two integer numbers $a_i$ and $b_i$ ( $1$ $\leq$ $a_i$ , $b_i$ $\leq$ $n$ , $a_i$ $\neq$ $b_i$ ) - meaning members $a_i$ and $b_i$ are friends.

First line of output should specify the number of members who are keeping their personal token.

The second line should contain space separated list of members who are keeping their personal token.

Each of the following $k$ lines should contain three space separated numbers, representing friend pairs and number of tokens each of them gets on behalf of their friendship.