Internet Problem Solving Contest

• Easy input data set – F1
• Hard input data set – F2 (generator)

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.

Problem statement

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.

Input specification

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 t_i, a_i, b_i (1 ≤ t_i ≤ 2; 1 ≤ a_i, b_i ≤ n; a_i ≠ b_i) describing event i. If t_i is 1, man a_i and man b_i meet. If t_i is 2, woman a_i and woman b_i meet.

In the easy subproblem F1, 2 ≤ n ≤ 1 500 and 1 ≤ q ≤ 2 000.

In the hard subproblem F2, 2 ≤ n ≤ 1 000 000 and 1 ≤ q ≤ 1 000 000. Because the input file size for subproblem F2 is about 50 MB, you cannot download it directly. Instead, we have provided a small Python 2 program that will generate the file f2.in when executed.

Output specification

For each test case: Let y_i be the number of familiar pairs of couples after event i. Then, let z_i be i ⋅ y_i. Output one line with a single number: the sum of z₁ + … + z_q modulo 10⁹ + 7.

Example

Input:

1

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

Output:

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.