数据分割

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

小w来到百度之星的赛场上,准备开始实现一个程序自动分析系统。

这个程序接受一些形如$x_i = x_j$ 或 $x_i \neq x_j$ 的相等/不等约束条件作为输入,判定是否可以通过给每个 w 赋适当的值,来满足这些条件。

输入包含多组数据。
然而粗心的小w不幸地把每组数据之间的分隔符删掉了。
他只知道每组数据都是不可满足的,且若把每组数据的最后一个约束条件去掉,则该组数据是可满足的。

请帮助他恢复这些分隔符。

Input

第$1$行:一个数字$L$,表示后面输入的总行数。

之后$L$行,每行包含三个整数,$i,j,e$,描述一个相等/不等的约束条件,若$e=1$,则该约束条件为$x_i = x_j$ ,若$e=0$,则该约束条件为 $x_i \neq x_j$ 。

$ i,j,L \leq 100000$

$x_i , x_j \leq L $

Output

输出共$T+1$行。

第一行一个整数$T$,表示数据组数。

接下来$T$行的第$i$行,一个整数,表示第i组数据中的约束条件个数。

Sample Input

6 2 2 1 2 2 1 1 1 1 3 1 1 1 3 1 1 3 0

Sample Output

1 6

Hint

liuyiding

Source

2017"百度之星"程序设计大赛 - 初赛(A)

提交代码