BubbleSquare Tokens

题意翻译

题目大意： 给出一张n个点，k条边的无自环图。你可以在每个点上放或者不放1个币，在每条边放0或1或2个币。每个点的权值为自己点上的币数量加与自己相连的边上的币数量。构造一种方案，使得图上任两个有边相连的点的权值不同。 题目输出要求： 第一行输出1个数num表示放上1个币的点数量。 接下来一行num个数表示放上1个币的点的编号。 接下来k行表示每条边放的币的数量。

题目描述

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.

输入输出样例

输入样例 #1

2 1
1 2

输出样例 #1

1
1 
1 2 0

输入样例 #2

3 3
1 2
1 3
2 3

输出样例 #2

0
1 2 0
2 3 1
1 3 2

说明

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

题意翻译

题目大意： 给出一张n个点，k条边的无自环图。你可以在每个点上放或者不放1个币，在每条边放0或1或2个币。每个点的权值为自己点上的币数量加与自己相连的边上的币数量。构造一种方案，使得图上任两个有边相连的点的权值不同。 题目输出要求： 第一行输出1个数num表示放上1个币的点数量。 接下来一行num个数表示放上1个币的点的编号。 接下来k行表示每条边放的币的数量。