수의사 동욱이는 동물병원을 새로 차렸다. 동욱이의 동물병원에는 N개의 병실이 있으며 각각 1 이상 N 이하의 서로 다른 정수 번호가 붙어있다. 일부 병실에는 통로가 있는데, 통로는 서로 다른 두 병실을 양방향으로 연결하며 총 N-1개 있다. 어떤 두 병실 사이를 선택하더라도 통로를 이용해서 이동 가능하다.

동욱이의 동물병원에서 반려동물이 수시로 입원 또는 퇴원한다. 입원하는 반려동물은 개 또는 고양이이며, 하나의 병실에는 오직 한 마리의 동물만 입원할 수 있다. 휴식 시간에 입원한 동물들이 통로를 이용해 움직일 수 있으나, 체계적인 관리를 위해 동욱이는 새로운 동물이 입원하거나 기존 동물이 퇴원하기 직전에는 입원한 동물들을 원래 위치로 옮긴다.

휴식시간에 고양이와 개가 서로 만난다면 돌발상황이 발생할 수 있기 때문에, 동욱이는 일부 통로를 폐쇄하여 개와 고양이가 서로 만나지 못하도록 하려고 한다. 통로 폐쇄는 꽤 번거로운 일이라서, 동욱이는 통로를 가능한 한 적게 폐쇄하여 목적을 달성하려고 한다.

앞으로 있을 Q개의 입/퇴원 일정이 주어지면 각 일정 이후 폐쇄하는 통로의 최소 수를 구하는 프로그램을 작성하여라.

#4682 upload 4 done 2 how_to_reg 2 call_split Subtask

Cats or Dogs timer 3s memory 512MB

#4682
Subtask

Cats or Dogs 3s 512MB