Description
有n对夫妇,一开始夫妇之间互不认识,若两男或两女成为朋友,称他们为"熟人","熟人"关系具有传递性,即若a熟b且b熟c则a熟c.若两组夫妇的丈夫互相为熟人且妻子也相互为熟人则称他们为"熟悉的一对",现在给出q个事件,每个事件会使得两男或两女成为朋友,并在每次事件之后计算"熟悉的一对"的个数.
Input
第一行一个数T表示数据组数
接下来n,q表示对数和事件数
接下来q行,每行t,a,b,若t=1,表示男a和男b成为朋友,t=2,表示女a和女b成为朋友
Output
设当前是第i个操作,y_i为本次事件之后的答案,令z_i=i*y_i,请输出z_1+z_2+...+z_q模10^9+7
Sample Input
13 5
1 1 2
2 1 3
1 2 3
1 3 1
2 2 1
Sample Output
22样例解释
1*0+2*0+3*1+4*1+5*3=22
Hint
T<=8
n,q<=10^6
