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
注意
在第一个测试用例中,只有第一个成员会保留其个人令牌,并且不会因第一个和第二个成员之间的友谊而奖励任何令牌。
在第二个测试用例中,没有任何成员会保留他们的个人令牌。第一个成员将收到两个代币(用于与第三个成员的友谊),第二个成员将收到一个代币(用于与第三个成员的友谊),第三个成员将收到三个代币(用于与第一个和第二个成员的友谊)。