unmerge 로직만 붙들고 있다가 시간을 너무 많이 소모했네요..
제 경우에는 unmerge가 아니라 merge로직이 문제였습니다.
노드 A, 노드 B, 노드 C가 있을 때
B가 C의 부모인 상태에서 A와 C를 병합하려고 하면
B와 C의 부모를 모두 업데이트해 주어야 합니다. C의 부모만 A로 수정하면 문제가 발생합니다.

아래는 제가 찾은 반례입니다.
["UPDATE 1 1 A", "UPDATE 2 2 B", "UPDATE 3 3 C", "UPDATE 4 4 D", "MERGE 1 1 2 2", "MERGE 3 3 4 4", "MERGE 1 1 4 4", "UNMERGE 3 3", "PRINT 1 1", "PRINT 2 2", "PRINT 3 3", "PRINT 4 4"]
답은 ["EMPTY", "EMPTY", "A", "EMPTY"]가 나와야 합니다. ["A", "A", "EMPTY", "A"]나 ["EMPTY", "EMPTY", "A", "A"] 같은 이상한 답이 나오지 않는지 확인해 주세요.