방 청소

• 술병에 대해서 처리해야 하는 오퍼레이션이 복잡해보이는데, 실제로는 술병을 몇번째 서랍에 보관해야 할지를 구할 필요가 없고 보관할지 마실지만 결정하면 된다.
• 서랍 Ai와 Bi를 한 그룹으로 묶으면, 그룹안에 빈 자리가 있으면 당연히 보관 가능. 그룹 안에 이미 다른 술병이 들어있을때, 그 술병을 기준으로 한 그룹에 빈 자리가 있으면, 그 술병을 다른 위치로 옮기고 현재 술병을 보관 가능. 바꿔서 말하면, Ai가 포함된 그룹과 Bi가 포함된 그룹을 묶어서 한 그룹으로 묶은 뒤에, 그룹 안에 빈 서랍이 있으면 보관 가능하다.
• 그룹을 묶는것은 Disjoint Set을 써서 처리하면 간단하다. 그룹의 빈 서랍의 갯수는 따로 저장해놓고서, 그룹을 묶을때마다 업데이트해주면 된다.
• 매 쿼리당, union만 한번씩 해주면 되니까 O(α(L))에 처리가능하고, N개의 술병에 대해서 처리하는데에는 O(N*α(L))이 걸린다.

"""Solution code for "BOJ 9938. 방 청소".

- Problem link: https://www.acmicpc.net/problem/9938
- Solution link: http://www.teferi.net/ps/problems/boj/9938

Tags: [Disjoint set]
"""

import sys
from teflib import disjointset


def main():
    N, L = [int(x) for x in sys.stdin.readline().split()]
    A_and_B = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    dsu = disjointset.DisjointSet(L)
    empty_drawer = [1] * L
    for a_i, b_i in A_and_B:
        a_set, b_set = dsu.find(a_i - 1), dsu.find(b_i - 1)
        if a_set != b_set:
            merged_set = dsu.union(a_set, b_set)
            empty_drawer[merged_set] = empty_drawer[a_set] + empty_drawer[b_set]
        else:
            merged_set = a_set
        if empty_drawer[merged_set] == 0:
            print('SMECE')
        else:
            empty_drawer[merged_set] -= 1
            print('LADICA')


if __name__ == '__main__':
    main()

• Dependency: teflib.disjointset.DisjointSet