🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cù lao Tân Lộc giữa sông Hậu có ~N~ ấp, đánh số từ ~1~ đến ~N~. Ấp nọ cách ấp kia bởi những con rạch nhỏ, nên muốn qua lại thì phải bắc cầu khỉ. Năm nay xã giao cho thầy Sơn lập phương án bắc cầu khỉ cho cả cù lao.

Thầy Sơn làm việc rất cẩn thận: trong ~Q~ ngày, mỗi ngày thầy ghi vào sổ một phương án mới — là một danh sách các cây cầu, xếp theo đúng thứ tự được thêm vào. Phương án của ngày ~0~ là danh sách rỗng (chưa có cầu nào). Phương án của ngày ~i~ ~(1 \le i \le Q)~ được lập theo một trong ba cách:

• 1 u v: chép lại phương án ngày ~i-1~ rồi thêm vào cuối một cây cầu nối ấp ~u~ với ấp ~v~ ~(u \ne v)~. Có thể giữa ~u~ và ~v~ đã có cầu, hoặc đã đi lại được với nhau từ trước.
• 2 t: chép lại phương án ngày ~i-1~ rồi bỏ đi ~t~ cây cầu được thêm sau cùng của phương án đó (dữ liệu bảo đảm phương án ngày ~i-1~ có ít nhất ~t~ cây cầu).
• 3 k: lấy lại y nguyên phương án của ngày ~k~ ~(0 \le k < i)~ — kể cả thứ tự các cây cầu.

Cuối mỗi ngày, thầy Sơn muốn biết phương án vừa lập "tốt" tới đâu: có bao nhiêu cặp ấp ~\{x, y\}~ ~(x < y)~ mà người dân có thể đi từ ấp ~x~ tới ấp ~y~ chỉ bằng các cây cầu trong phương án của ngày hôm đó.

Hãy giúp thầy Sơn trả lời cho cả ~Q~ ngày.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(2 \le N \le 2 \times 10^5;~ ~1 \le Q \le 2 \times 10^5)~.
• Dòng thứ ~i~ trong ~Q~ dòng tiếp theo mô tả phương án ngày ~i~, có một trong ba dạng 1 u v ~(1 \le u, v \le N,\ u \ne v)~, 2 t ~(t \ge 1)~ hoặc 3 k ~(0 \le k < i)~ như mô tả ở trên.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~i~ là số cặp ấp đi lại được với nhau theo phương án của ngày ~i~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N, Q \le 2000~.
• Subtask 2 (~20\%~ số điểm): chỉ có các phương án dạng 1 u v.
• Subtask 3 (~25\%~ số điểm): chỉ có các phương án dạng 1 u v và 2 t.
• Subtask 4 (~35\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

5 8
1 1 2
1 2 3
1 4 5
2 2
3 3
1 3 1
2 3
3 5

Sample Output 1

1
3
4
1
4
4
1
4

Giải thích

• Ngày 1 (1 1 2): cầu (1–2); các nhóm {1, 2}; số cặp: 1.
• Ngày 2 (1 2 3): cầu (1–2), (2–3); các nhóm {1, 2, 3}; số cặp: 3.
• Ngày 3 (1 4 5): cầu (1–2), (2–3), (4–5); các nhóm {1, 2, 3}, {4, 5}; số cặp: 3 + 1 = 4.
• Ngày 4 (2 2): cầu (1–2); các nhóm {1, 2}; số cặp: 1.
• Ngày 5 (3 3): cầu (1–2), (2–3), (4–5); các nhóm {1, 2, 3}, {4, 5}; số cặp: 4.
• Ngày 6 (1 3 1): cầu (1–2), (2–3), (4–5), (3–1); các nhóm {1, 2, 3}, {4, 5}; số cặp: 4.
• Ngày 7 (2 3): cầu (1–2); các nhóm {1, 2}; số cặp: 1.
• Ngày 8 (3 5): cầu (1–2), (2–3), (4–5); các nhóm {1, 2, 3}, {4, 5}; số cặp: 4.

Ngày 7 bỏ đi ~3~ cây cầu được thêm sau cùng của phương án ngày 6, đó là (3–1), (4–5), (2–3).

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).