Sau khi tốt nghiệp Đại học Sư phạm Đà Nẵng, Ngạn trở về công tác tại trường tiểu học làng Đo Đo. Tiếp thu những công nghệ tiến bộ ở thành phố, đồng thời muốn níu giữ những ký ức đẹp về cuộc tình đơn phương hàng thập kỷ của mình, thầy giáo Ngạn đã phổ cập cho học sinh trong trường về cách thức viết các confession để mỗi học sinh có cơ hội thú nhận ẩn danh tình cảm thầm kín với crush của mình. Nhưng vì kết nối internet còn khá chậm và chập chờn, các confession đều phải viết ra giấy, và thầy Ngạn cũng đành phải kiêm luôn công việc chuyển phát confession giúp các học sinh của mình.

Vào niên khóa mà Ngạn chuyển về, trường tiểu học làng Đo Đo có N học sinh mới nhập học, được đánh số từ 1 đến N. Mỗi một ngày trong M ngày đầu tiên của năm học, tại trường đã xảy ra một trong ba loại sự kiện sau:

- Sự kiện loại 1: Học sinh x bắt đầu crush học sinh y (x ≠ y, 1 ≤ x, y ≤ N). Nói cách khác, học sinh y chính thức trở thành crush của học sinh x. Trước thời điểm này, học sinh x chưa từng có một crush nào (bởi vì người làng Đo Đo vô cùng chung thủy với crush của mình nên không hề xảy ra một trường hợp uncrush hoặc crush-nhiều-người-cùng-lúc nào). Mỗi người làng Đo Đo cũng mang trong mình một đẳng cấp tiềm ẩn và ai trong số họ cũng chỉ crush người có đẳng cấp cao hơn mình.

- Sự kiện loại 2: Học sinh x (1 ≤ x ≤ N) nào đó được Ngạn chuyển cho một confession đến từ một học sinh khác trường. Sau khi đọc xong confession này, học sinh x sẽ đem khoe và chia sẻ cho crush của mình cùng đọc. Và sau khi crush của học sinh x đọc xong, cậu ấy sẽ tiếp tục chia sẻ cho crush của cậu ấy cùng đọc. Mọi chuyện sẽ lặp lại cho đến khi confession được đọc xong bởi một học sinh không có crush.

- Sự kiện loại 3: Thầy Ngạn thắc mắc và tìm hiểu xem học sinh x đã đọc được confession thứ i, theo trình tự thời gian được gửi, hay chưa (1 ≤ x ≤ N, i không vượt quá số confession đã được thầy Ngạn chuyển phát). 

Những thắc mắc của thầy Ngạn trở thành vấn đề nan giải vì N khá lớn, nên thầy đã gửi chúng, cùng thông tin chi tiết về tất cả các sự kiện loại 1 và loại 2, cho Định để nhờ giải đáp giúp. Nhưng giờ đây, quỹ thời gian của Định chỉ còn dành duy nhất cho những buổi nhảy đầm đầy hoan lạc và đê mê cùng Hà Lan và Bích Hoàng, nên cậu đành chuyển giao những tò mò đầy khó hiểu và tọc mạch của thầy Ngạn đến cho các bạn. Hãy giúp Định được dành trọn năng lượng và thời gian của mình để ăn chơi nhé!

Định dạng input:

- Dòng đầu chứa hai số nguyên dương N và M.

- Dòng thứ i trong M dòng tiếp theo bắt đầu bằng số nguyên 1 nếu ngày thứ i diễn ra sự kiện loại 1, và theo sau đó là hai số nguyên dương x, y. Tương tự, nó sẽ bắt đầu bằng số nguyên 2 hoặc 3 cùng các dữ liệu theo sau tương ứng nếu ngày thứ i diễn ra sự kiện loại 2 hoặc sự kiện loại 3.

Định dạng output: