#4153. [Ipsc2015]Familiar Couples

题目描述

有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