← 返回题目列表

Codeforces · 1423/N

N. BubbleSquare 代币

中文机器翻译题面 查看原题

BubbleSquare 社交网络正在庆祝 $$$13^{th}$$$ 周年纪念日,并用特别版 BubbleSquare 代币奖励其会员。每个成员都会收到一个个人代币。此外,每个成员在网络上拥有的每个朋友都会获得两个额外的代币。然而,有一个转折点——每个人最终都会从所有朋友那里获得不同数量的代币。每个成员可以返回一个收到的令牌。此外,每两个朋友可以同意各自归还他们代表友谊而获得的一两个令牌。

输入

输入的第一行包含两个整数 $$$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$$$ 是朋友。

输出

输出的第一行应指定保留个人令牌的成员数量。

第二行应包含保留个人令牌的成员的空格分隔列表。

以下 $$$k$$$ 行中的每一行都应包含三个空格分隔的数字,代表朋友对以及他们每个人代表其友谊获得的代币数量。

示例

输入 #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

注意

在第一个测试用例中,只有第一个成员会保留其个人令牌,并且不会因第一个和第二个成员之间的友谊而奖励任何令牌。

在第二个测试用例中,没有任何成员会保留他们的个人令牌。第一个成员将收到两个代币(用于与第三个成员的友谊),第二个成员将收到一个代币(用于与第三个成员的友谊),第三个成员将收到三个代币(用于与第一个和第二个成员的友谊)。