시간 제한메모리 제한제출정답맞힌 사람정답 비율
15 초 1024 MB0000.000%

## 문제

The rural village Spišský Štvrtok is populated by n married couples – n men and n women, both labeled from 1 to n in such a way that for each i, man i is married to woman i.

Whenever two men meet in the village pub, they become friends. Friendship lasts forever. We say two men are acquaintances if they are friends, or if they have a mutual acquaintance. This means that if man a and man b become friends, they also become acquaintances, and all acquaintances of a become acquainted with all acquaintances of b. Similarly, two women can become friends. We say two women are acquaintances if they are friends, or if they have a mutual acquaintance.

Couples living in the village can be familiar with each other. We say couple a is familiar with couple b (they’re a “familiar pair of couples”) if man a and man b are acquaintances, and woman a and woman b are also acquaintances.

At the beginning, no two people are friends with each other. Then q events happen in sequence. Each event is either a meeting between two men or a meeting between two women. If the two people who met aren’t friends yet, they become friends.

After each event, compute the number of familiar pairs of couples. That is, count the number of pairs a, b (a ≠ b) such that man a is acquainted with man b and woman a is acquainted with woman b. Note that the pairs are unordered – for example, 1, 2 is the same pair as 2, 1.

## 입력

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with a line containing the integers n and q. The i-th of the following q lines contains integers ti, ai, bi (1 ≤ ti ≤ 2; 1 ≤ ai, bi ≤ n; ai ≠ bi) describing event i. If ti is 1, man ai and man bi meet. If ti is 2, woman ai and woman bi meet.

## 출력

For each test case: Let yi be the number of familiar pairs of couples after event i. Then, let zi be i ⋅ yi. Output one line with a single number: the sum of z1 + … + zq modulo 109 + 7.

## 서브태스크

번호배점제한
Easy1

2 ≤ n ≤ 1 500 and 1 ≤ q ≤ 2 000.

Hard2

2 ≤ n ≤ 1 000 000 and 1 ≤ q ≤ 1 000 000.

## 예제 입력 1

1

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


## 예제 출력 1

22


## 힌트

After event 3, couple 1 is familiar with couple 3. After event 5, all couples are familiar with each other. Together, we get 1 ⋅ 0 + 2 ⋅ 0 + 3 ⋅ 1 + 4 ⋅ 1 + 5 ⋅ 3 = 22.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.