Nguồn đề : https://www.spoj.com/problems/CHAIN/

Khi ac bài này tại judge của clb các bạn hãy thử nộp lại ở link trên, thứ nhất là ủng hộ tác giả hoặc dịch giả, hai và vì test ở judge clb là thành viên clb sinh có thể xảy ra sai sót.

Có 3 loài động vật A, B và C. A ăn B, B ăn C và C ăn A.

Bạn có n con vật, được đánh số từ 1 đến n. Mỗi con trong số chúng thuộc 1 trong 3 loài trên (A, B, C).

Hôm nay Thu nói với chúng ta k thông tin về những con vật này. Mỗi thông tin có dạng sau:

• 1 x y : Con x và y là cùng loài.
• 2 x y : Con x ăn con y.

Một vài thông tin là đúng một, vài thông tin là sai. Một thông tin chỉ sai khi thỏa mãn một trong 3 điều kiện sau, nếu không thông tin đó là đúng.

• x hoặc y lớn hơn n.
• x ăn x
• Trái ngược với một thông tin đúng trước đó.

Input

Đầu vào chứa t ~(1 \le t \le 100 )~ test, mối test có dạng như sau:

Dòng đầu tiên chứa 2 số nguyên n ~(1 \le n \le 5.10^4 )~ và k ~(1 \le k \le 10^5 )~

k dòng tiếp theo, mỗi dòng chứa 3 số nguyên D ~(1 \le D \le 2 )~ X và Y.

Kết quả

Với mỗi test hãy in ra số lượng thông tin sai

Sample Input

2
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
10 6
1 1 2
1 5 6
1 6 1
1 6 2
2 1 3
1 6 3

Sample Output

3
1