solution

Nhược điểm nổi tiếng của đếm tham chiếu (reference counting) là không thể tự thu hồi các chu trình tham chiếu (reference cycle) không còn được gốc (root) trỏ tới — vì các object trong chu trình vẫn giữ tham chiếu lẫn nhau nên refcount không bao giờ về $0$, dẫn tới rò rỉ bộ nhớ (memory leak).

Cho $n$ object (id $1..n$), mỗi object có bộ đếm tham chiếu $rc$ (ban đầu $0$). Có $q$ thao tác lần lượt:

• ROOT r: thêm một tham chiếu gốc tới $r$ ($rc_r \mathrel{+}= 1$).
• UNROOT r: bỏ một tham chiếu gốc khỏi $r$ ($rc_r \mathrel{-}= 1$; đảm bảo có ít nhất một tham chiếu gốc đang tồn tại tới $r$).
• REF a b: object $a$ (còn sống) thêm một tham chiếu tới object $b$ (còn sống) ($rc_b \mathrel{+}= 1$).
• UNREF a b: object $a$ bỏ một tham chiếu tới $b$ ($rc_b \mathrel{-}= 1$; đảm bảo tham chiếu này đang tồn tại).

Mỗi khi $rc$ của một object về $0$ (do UNROOT/UNREF), object đó lập tức bị giải phóng theo kiểu cascade: mọi tham chiếu mà chính nó đang giữ tới các object khác cũng bị hủy (refcount các object bị trỏ tới giảm tương ứng), có thể kéo theo giải phóng dây chuyền tiếp. (Đề bài đảm bảo mọi thao tác chỉ nhắc tới object còn sống tại thời điểm đó.)

Sau khi xử lý xong tất cả thao tác, tìm các object rác chu trình bị rò rỉ: object còn "sống" (chưa từng bị giải phóng, $rc>0$) nhưng không thể với tới được từ bất kỳ tham chiếu gốc nào hiện tại (qua các cạnh tham chiếu còn tồn tại) — chính là bộ nhớ mà reference counting đã "bỏ sót", cần một GC dạng tracing (như mark-sweep) mới thu hồi được. (Object chưa từng được tham chiếu lần nào, $rc=0$ từ đầu tới cuối, không được tính là rò rỉ.)

Yêu cầu: in danh sách id object rò rỉ (tăng dần), hoặc NONE; dòng tiếp theo in số lượng object rò rỉ.

Ví dụ: $n=2$. ROOT 1; REF 1 2; REF 2 1; UNROOT 1. Sau UNROOT 1: $rc_1=1$ (còn tham chiếu từ object $2$), $rc_2=1$ (còn tham chiếu từ object $1$) — cả hai vẫn "sống" theo refcount nhưng không còn gốc nào trỏ tới, tạo thành chu trình rò rỉ: in 1 2 và số lượng 2.