Solution SUPERPRO :

• Gọi cnt[u] là số lượng đỉnh cha trực tiếp chưa xóa của đỉnh u.
• Gọi cost[u] là số lượng bước nhảy ít nhất để xóa được đỉnh u.
• Ban đầu gán cost[u] = -1 với mọi u, coi như đỉnh này chưa đi tới.
• Sử dụng BFS từ các đỉnh u có cnt[u] ban đầu bằng 0, và gán cost[u] = 0 nếu nhãn của đỉnh u là kí tự A hoặc kí tự C ngược lại thì gán cost[u] = 1.
• Khi BFS đến đỉnh u thì ta sẽ chạy v là các đỉnh con trực tiếp của đỉnh u và cnt[v] sẽ bị trừ đi 1 (đã xóa đỉnh u nên số lượng nút cha chưa được xóa của v bị trừ đi 1).
• Nếu cnt[v] == 0 thì chạy k là các nút cha trực tiếp của nút v và xét những trường hợp sau đây để tính được cost[v] :
• Kiểm tra xem khi xóa đỉnh k thì giáo sư hiện đang ở hành tinh A hay hành tinh B, nếu cost[k] lẻ thì giáo sư đang ở hành tinh B ngược lại thì giáo sư đang ở hành tinh A.
• Khi đã xác định được hành tinh của giáo sư, nếu đỉnh v có thể xóa ở hành tinh hiện tại của giáo sư khi xóa đỉnh k thì cost[v] = max(cost[v], cost[k]) ngược lại cost[v] = max(cost[v], cost[k] + 1).
• Yên tâm là cost[k] không thể bằng -1 vì khi đang xét tới đỉnh v thì đỉnh k đã được xét trước đó và đã có một giá trị cost đúng.
• Sau khi đã tính được cost[v] thì push v vào queue và tiếp tục BFS cho tới khi không còn đỉnh nào ở trong queue.
• Khi đã BFS xong, việc chúng ta cần làm là kiểm tra xem tất cả các đỉnh đã được xóa hay chưa, để làm đươc thì ta chỉ cần kiểm tra xem có tồn tại một cost[u] == -1 với mọi u hay không, nếu có thì in ra -1 ngược lại thì in ra max của cost[u] với mọi u.
• Độ phức tạp O(n + m).