Tô màu nhị phân
Cho $N$ chấm tròn. Phúc muốn tô màu các chấm tròn bằng 2 màu xanh và đỏ và tô theo một bản vẽ. Vì vậy cậu có $Q$ truy vấn. Có 3 loại truy vấn:
GIONG u v: Cậu muốn tô màu sao cho chấm tròn thứ $u$ cùng màu với chấm tròn $v$;KHAC u v: Cậu muốn tô màu sao cho chấm tròn thứ $u$ khác màu với chấm tròn $v$;HOI u v: Cậu muốn biết, bằng những dữ liệu đã có, màu của chấm tròn $u$ có cùng với chấm tròn $v$ hay không?
Hãy trả lời các truy vấn HOI.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N, Q \ (1\le N, Q \le 10^5)$;
- $Q$ dòng tiếp theo, mỗi dòng chứa các truy vấn theo mẫu trên $(1\le u,v \le N)$.
Dữ liệu đảm bảo không có mâu thuẫn giữa các truy vấn.
Kết quả
- Với mỗi truy vấn
HOI, in raGIONGnếu chúng cùng màu,KHACnếu chúng khác màu vàKHONGnếu không rõ câu trả lời dựa trên những dữ liệu có sẵn.
Ví dụ
Ví dụ 1
input
4 6
HOI 1 2
GIONG 1 2
KHAC 2 3
KHAC 1 4
HOI 1 3
HOI 2 4
output
KHONG
KHAC
KHAC
Comments