BZPRO
#4153. [Ipsc2015]Familiar Couples
内存限制：256 MiB
时间限制：15 Sec
提交
提交记录
讨论
题目描述
有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
BZPRO