Đêm giáng sinh đang cận kề, đôi tình nhân Nauq và Hana quyết định mua cho mình một cây thông và trang trí nó. Nauq và Hana mua một bộ đèn gồm ~n~ bóng đèn để nối chúng với nhau và treo lên cây thông. Một bóng đèn có hai chế độ phát sáng là sáng màu xanh lá hoặc sáng màu đỏ. Nauq và Hana cho rằng một cây thông được gọi là thõa mãn tính thẩm mỹ khi hai bóng đèn bất kì được nối với nhau phải khác màu nhau.
Để không khí buổi trang trí cây thông của cả hai thêm vui vẻ, Hana quyết định chơi một trò chơi với Nauq gồm hai thao tác như sau:
Hana chọn ra hai bóng đèn ~x~ và ~y~. Nếu hai bóng đèn này đang được nối trong hai cụm đèn khác nhau, Hana sẽ nối chúng với nhau và thực hiện đổi màu đèn sao cho chúng thỏa mãn tính thẩm mỹ mà cả hai đã đưa ra. Ngược lại, nếu chúng cùng được nối trong một cụm đèn thì Hana không làm gì cả.
Hana đưa ra hai bóng đèn ~x~ và ~y~. Nếu hai bóng đèn này đang được nối trong cùng một cụm đèn, Hana sẽ hỏi Nauq rằng liệu hai bóng đèn này có cùng màu hay không. Ngược lại, nếu hai bóng đèn này không nằm trong cùng một cụm đèn thì Hana sẽ yêu cầu Nauq nói "Merry Christmas!".
Lưu ý: Ban đầu chưa có bóng đèn nào được nối với nhau.
Input
Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ — lần lượt là số bóng đèn và số thao tác mà Hana sẽ chơi với Nauq (~1 \le n, m \le 2 \times 10^5~).
Tiếp theo gồm ~m~ dòng mô tả các thao tác của Hana có dạng như sau:
Thao tác loại một: "~1~ ~x~ ~y~" (~1 \le x, y \le n~).
Thao tác loại hai: "~2~ ~x~ ~y~" (~1 \le x, y \le n~).
Output
In ra mỗi dòng là "Yes", "No" lần lượt ứng mỗi mỗi thao tác loại hai nếu hai bóng đèn được hỏi có cùng màu hay không. Nếu thao tác loại hai này Hana hỏi Nauq hai bóng đèn mà không được nối trong cùng một cụm đèn thì in ra "Merry Christmas!".
Scoring
Subtask | Điểm | Ràng buộc |
---|---|---|
~1~ | ~30 \%~ | ~n, m \le 5000~ |
~2~ | ~30 \%~ | Mọi thao tác loại một đều được thực hiện trước mọi thao tác loại hai |
~3~ | ~40 \%~ | Không có ràng buộc gì thêm |
Sample Input 1
3 4
1 1 2
1 2 3
2 1 2
2 1 3
Sample Output 1
No
Yes
Sample Input 2
6 8
1 1 4
2 1 4
1 1 2
2 2 4
1 2 5
1 4 6
2 1 5
2 1 6
Sample Output 2
No
Yes
Yes
Yes
Sample Input 3
3 2
1 1 2
2 1 3
Sample Output 3
Merry Christmas!
Notes
Giải thích test ví dụ thứ nhất: Sau hai thao tác đầu tiên, các bóng đèn được nối lần lượt theo thứ tự là ~1~ - ~2~ - ~3~. Do đó, ta có thể có hai cách bật đèn là đỏ - xanh - đỏ hoặc xanh - đỏ - xanh ứng với các đèn ~1~ - ~2~ - ~3~.
Giải thích test ví dụ thứ ba: Trong thao tác thứ hai, bóng đèn ~1~ và bóng đèn ~3~ không nằm trong một cụm đèn trước đó nên Nauq cần nói "Merry Christmas!"
Bình luận