서로 아는 부부 쌍

마을 스피시스키 슈트보르톡에는 $n$쌍의 부부가 살고 있다. 남자 $n$명과 여자 $n$명이 있으며, 두 집단 모두 1부터 $n$까지 번호가 매겨져 있다. 모든 $i$에 대해 남자 $i$는 여자 $i$와 결혼한 사이이다.

마을 술집에서 두 남자가 만나면 둘은 친구가 된다. 친구 관계는 영원히 유지된다. 두 남자는 친구이거나 공통으로 아는 사람이 있으면 서로 아는 사이이다. 남자 $a$와 $b$가 친구가 되면 둘은 서로 아는 사이가 되고, $a$가 아는 모든 사람은 $b$가 아는 모든 사람과 서로 알게 된다. 여자도 같은 규칙을 따른다.

부부 $a$와 부부 $b$가 친숙한 부부 쌍이라는 것은 남자 $a$와 남자 $b$가 서로 아는 사이이고, 여자 $a$와 여자 $b$도 서로 아는 사이라는 뜻이다.

처음에는 아무도 친구가 아니다. 이후 $q$개의 사건이 순서대로 일어난다. 각 사건은 두 남자의 만남 또는 두 여자의 만남이다. 만난 두 사람이 아직 친구가 아니라면 친구가 된다. 매 사건 후에는 $a \neq b$인 쌍 $a, b$ 중에서 남자 $a$와 남자 $b$가 서로 아는 사이이고 여자 $a$와 여자 $b$도 서로 아는 사이인 쌍의 수를 센다. 쌍은 순서를 구분하지 않으므로 $1, 2$와 $2, 1$은 같은 쌍이다.

첫 줄에는 테스트 케이스의 수 $t$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.

각 테스트 케이스의 첫 줄에는 정수 $n$과 $q$가 주어진다. 이어지는 $q$개의 줄 중 $i$번째 줄에는 정수 $t_i$, $a_i$, $b_i$가 주어진다 ($1 \le t_i \le 2$, $1 \le a_i, b_i \le n$, $a_i \neq b_i$). $t_i$가 1이면 남자 $a_i$와 남자 $b_i$가 만나는 것이고, 2이면 여자 $a_i$와 여자 $b_i$가 만나는 것이다.

각 테스트 케이스마다 사건 $i$ 이후의 친숙한 부부 쌍의 수를 $y_i$라 하고, $z_i = i \cdot y_i$라 하자. $z_1 + \cdots + z_q$를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

사건 3 이후 부부 1과 부부 3은 친숙하다. 사건 5 이후에는 모든 부부가 서로 친숙하다. 따라서 합은 $1 \cdot 0 + 2 \cdot 0 + 3 \cdot 1 + 4 \cdot 1 + 5 \cdot 3 = 22$이다.