Đồ thị A-Z

Cho một đồ thị có hướng gồm $n$ đỉnh. Mỗi cung có hướng được gắn một ký tự chữ cái Latinh thường. Ban đầu đồ thị không có cung nào.

Bạn cần xử lý $m$ truy vấn thuộc một trong ba loại:

• "+ u v c": thêm cung có hướng từ $u$ đến $v$ với nhãn $c$. Đảm bảo tại thời điểm này chưa có cung $(u,v)$ trong đồ thị.
• "- u v": xóa cung có hướng từ $u$ đến $v$. Đảm bảo tại thời điểm này đồ thị đang có cung $(u,v)$.
• "? k": tìm một dãy $k$ đỉnh $v_1,v_2,\dots ,v_k$ sao cho tồn tại đồng thời cả hai đường đi $v_1\to v_2\to \cdots \to v_k$ và $v_k\to v_{k-1}\to \cdots \to v_1$; đồng thời nếu ghi lại các ký tự dọc theo mỗi đường đi thì hai xâu thu được phải bằng nhau. Được phép thăm lại một đỉnh bao nhiêu lần tùy ý.

Với mỗi truy vấn loại thứ ba, in ra YES nếu tồn tại dãy như mô tả, ngược lại in ra NO.

Lưu ý: đường đi $v_1\to v_2\to \cdots \to v_k$ sử dụng các cung $(v_1,v_2),(v_2,v_3),\dots ,(v_{k-1},v_k)$, còn đường đi ngược sử dụng các cung $(v_k,v_{k-1}),\dots ,(v_2,v_1)$. Do đó mỗi cặp đỉnh liên tiếp trong dãy phải có cung theo cả hai chiều.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong ba định dạng ở trên.

Dữ liệu ra

Với mỗi truy vấn loại "? k", in ra YES hoặc NO trên một dòng riêng.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $1\le m\le 2·{10}^5$
• Với truy vấn thêm: $1\le u,v\le n$, $u\ne v$, $c$ là chữ cái Latinh thường.
• Với truy vấn xóa: $1\le u,v\le n$, $u\ne v$.
• Với truy vấn hỏi: $2\le k\le {10}^5$.
• Đảm bảo không thêm cung bị trùng và chỉ xóa cung đang tồn tại.
• Có ít nhất một truy vấn loại thứ ba.

Ví dụ