CF1423N.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.

BubbleSquare 社交网络正在庆祝其成立 $13^{th}$ 周年，并向其会员发放特别版 BubbleSquare 代币作为奖励。每位会员将获得一枚专属代币；此外，每位会员还可为其在该网络上的每一位好友额外获得两枚代币。但此处有一个特殊规则：每位会员最终所持有的代币总数必须与其所有好友的代币总数互不相同。每位会员可自愿退回一枚所获代币；此外，任意两位好友之间可协商一致，各自退回一枚或两枚他们因彼此好友关系而获得的代币。

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.

输入的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 12500$，$1 \leq k \leq 1000000$），分别表示社交网络中的成员数量和友谊关系数量。

接下来的 $k$ 行每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$），表示成员 $a_i$ 和 $b_i$ 是朋友。

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.

输出的第一行应指明保留个人代币的成员人数。

第二行应包含一个以空格分隔的列表，列出保留个人代币的成员。

接下来的 $k$ 行中，每行应包含三个以空格分隔的数字，分别表示一对朋友关系以及他们因该友谊各自获得的代币数量。

In the first test case, only the first member will keep its personal token and no tokens will be awarded for friendship between the first and the second member.

In the second test case, none of the members will keep their personal token. The first member will receive two tokens (for friendship with the third member), the second member will receive one token (for friendship with the third member) and the third member will receive three tokens (for friendships with the first and the second member).

在第一个测试用例中，只有第一位成员会保留其个人代币，且第一位成员与第二位成员之间的友谊不会获得任何代币。

在第二个测试用例中，没有任何成员会保留其个人代币。第一位成员将获得两个代币（来自与第三位成员的友谊），第二位成员将获得一个代币（来自与第三位成员的友谊），第三位成员将获得三个代币（来自与第一位和第二位成员的友谊）。