Vào khoảng thời gian nào đó năm nào đó, thời gian này đang hoành hành rất nhiều Ma sói. Tại một ngôi làng nhỏ ven sông gồm ~n~ người, nơi đây vốn bình yên và nhẹ nhàng trôi qua từng ngày, Bỗng một ngày nọ, Ma Sói xuất hiện làm đảo lộn cuộc sống của mọi người ở đây. Loài động vật này vô cùng khôn khéo, ban ngày thì chúng ở ngụy trang thành dân thường, còn đêm thì chúng trở về thân phận thật của mình và cắn con người. Chính vì vậy, cuộc sống của người dân tại ngôi làng ngày càng trở nên căng thẳng bởi sự nguy hiểm, sự sợ hãi. Không thể sống mãi trong lo sợ và căng thẳng như thế mãi, dân làng quyết định cùng nhau hợp sức lại để chống lại lũ Ma Sói kia. Nhưng cũng thật may mắn, trong làng cũng có một số người dân có năng lực đặc biệt giúp việc tìm ra Ma Sói phần nào bớt khó khăn hơn…

Dù hoảng sợ là thế, nhưng một số người dân trong đây lại thèm trà sữa!? Vì thế, bạn đến từ khu xóm "Tà tưa" mỗi ngày đều phải đi ship trà sữa cho người dân trong làng. Với năng lực đặc biệt của những người dân trong làng, trên bảng tin vào mỗi ngày đều cập nhật thêm một thông tin nào đó về sói như: "Trường là sói cô độc.", "Quang và Trường đều cùng một phe", "Quang và Trường có thể đều là sói, nhưng không có vụ Quang và Trường đều cùng là người", ~\ldots~.

Tuy nhiên với sự thông minh trời phú của mình, bạn nhận ra được điểm khác thường nếu xâu chuỗi tất cả thông tin đã nghe. Có tổng cộng ~q~ ngày, liệu bạn có thể tìm được điểm khác thường dựa vào các thông tin trên bảng tin hay không? Nếu có, hãy xác định thời điểm đầu tiên mà bạn tìm ra được điểm bất thường nhé.

Input

Dòng đầu tiên gồm một số nguyên ~t~ (~1 \le t \le 10^4~) — số lượng bộ test. Với mỗi bộ test:

Dòng đầu tiên của mỗi test gồm hai số nguyên ~n, q~ (~1 \le n \le 10^9~, ~1 \le q \le 10^5~) — số lượng người/sói trong làng và số lượng ngày.

Trong ~q~ dòng tiếp theo của test, mỗi dòng thuộc ~1~ trong ~3~ dạng sau:

• 1 x k: Thông tin cho biết ~x~ ~(1 \le x \le n)~ sẽ là người nếu ~k = 0~ và là sói nếu ~k = 1~.

• 2 x y k: Thông tin cho biết ~x~ ~(1 \le x \le n)~ cùng phe với ~y(1 \le y \le n)~ nếu ~k = 0~ và khác phe nếu ~k = 1~.

• 3 x u y v: Gồm hai mảnh thông tin dạng 1 x u và 1 y v. Thông tin cho biết có ít nhất một mảnh thông tin là sự thật.

Đảm bảo rằng tổng ~q~ của tất cả truy vấn không vượt quá ~10^5~.

Output

Gồm ~t~ dòng, mỗi dòng in thời điểm đầu tiên mà bạn tìm ra được điểm bất thường trong các thông tin đã nghe được. Còn nếu sau cả ~q~ ngày bạn vẫn không tìm ra được điểm bất thường thì in ra ~-1~.

Scoring

Sample Input 1

1
10062006 5
1 1 1
2 1 2 0
1 3 1
1 2 0
3 1 1 3 0

Sample Output 1

4

Notes

Bạn suy luận như sau:

• Thông tin ~1~: cư dân ~1~ là sói;

• Thông tin ~2~: cư dân ~2~ cùng phe cư dân ~1~, cư dân ~2~ là sói;

• Thông tin ~3~: cư dân ~3~ là sói;

• Thông tin ~4~: cư dân ~2~ là người, mâu thuẫn với thông tin ~2~.

Vậy thời điểm đầu tiên xuất hiện điểm bất thường là ~4~.