[Ipsc2015]Familiar Couples

时间限制:15s      空间限制:256MB

题目描述

有n对夫妇,一开始夫妇之间互不认识,若两男或两女成为朋友,称他们为"熟人","熟人"关系具有传递性,即若a熟b且b熟c则a熟c.若两组夫妇的丈夫互相为熟人且妻子也相互为熟人则称他们为"熟悉的一对",现在给出q个事件,每个事件会使得两男或两女成为朋友,并在每次事件之后计算"熟悉的一对"的个数.


输入格式

第一行一个数T表示数据组数
接下来n,q表示对数和事件数
接下来q行,每行t,a,b,若t=1,表示男a和男b成为朋友,t=2,表示女a和女b成为朋友


输出格式

设当前是第i个操作,y_i为本次事件之后的答案,令z_i=i*y_i,请输出z_1+z_2+...+z_q模10^9+7


样例输入

1
3 5
1 1 2
2 1 3
1 2 3
1 3 1
2 2 1

样例输出

22

样例解释
1*0+2*0+3*1+4*1+5*3=22



提示

T<=8
n,q<=10^6


题目来源

没有写明来源