낙하산 고리들

레오나르도 다 빈치의 《코덱스 아틀란티쿠스》에는 최초로 설계된 꽤 정교한 낙하산이 나온다. 이 낙하산은 피라미드 모양의 나무 골조에 씌운 우산 모양의 리넨 천으로 이루어져 있다.

스카이다이버 아드리안 니콜라스는 500년도 더 된 이 설계를 실제로 시험해 보았다. 이때 사람의 몸을 낙하산에 묶기 위해 현대식 초경량 구조를 사용했다. 우리는 리넨 천에도 걸 수 있는 고리 구조를 사용하려고 한다. 각 고리는 유연하면서도 튼튼한 소재로 만들어져 있으며, 모두 열고 닫을 수 있어 다른 고리와 자유롭게 연결할 수 있다.

체인은 고리 구조의 특별한 형태이다. 아래 그림처럼 각 고리가 인접한 고리와 (최대 두 개까지) 차례로 연결되어 시작과 끝이 있는 한 줄을 이룰 때, 이를 체인이라고 한다. 시작과 끝에 있는 고리는 각각 다른 고리 최대 하나와만 연결된다. 특히 고리가 하나뿐인 경우도 체인으로 본다.

하나의 고리가 세 개 이상의 다른 고리와 연결될 수도 있다. 이런 고리 구조에서 어떤 고리 하나를 열어 없앴을 때 남은 고리들이 모두 체인이 되면(또는 고리가 하나도 남지 않으면), 그 고리를 중요한 고리라고 부른다. 즉, 중요한 고리를 제거하면 체인들만 남는다.

아래 그림처럼 0번부터 6번까지 번호가 붙은 7개의 고리를 생각하자. 이 구조에는 중요한 고리가 2개 있다. 하나는 2번으로, 없애면 남은 고리들이 [1], [0, 5, 3, 4], [6]의 세 체인이 된다. 다른 하나는 3번으로, 없애면 [1, 2, 0, 5], [4], [6]의 세 체인이 된다. 그 밖의 고리를 없애면 체인이 아닌 부분이 남는다. 예를 들어 5번 고리를 없애면 [6]은 체인이지만 0, 1, 2, 3, 4번 고리로 이루어진 부분은 체인이 아니다.

여러분이 할 일은 주어지는 고리 구조에서 중요한 고리의 개수를 세는 것이다.

처음에는 서로 연결되지 않은 N개의 고리가 주어지고, 그다음 두 종류의 연산이 차례로 주어진다.

• Link(A, B) — A번 고리와 B번 고리를 서로 연결한다. A와 B는 서로 다르며, 이 시점에 두 고리는 아직 연결되어 있지 않음이 보장된다. 그 밖의 제약은 없다(물리적 조건과도 무관하다). Link(A, B)와 Link(B, A)는 같은 연산이다.
• CountCritical() — 현재 고리 구조에서 중요한 고리의 개수를 구해 출력한다.

첫째 줄에 고리의 개수 N과 연산의 개수 L이 주어진다. 이어지는 L개의 줄에는 각 연산이 순서대로 주어진다. 어떤 줄에 -1이 있으면 그 연산은 CountCritical()이고, 두 정수 A와 B가 있으면 Link(A, B)이다. 고리에는 0번부터 N − 1번까지 번호가 붙어 있다.

CountCritical() 연산이 주어질 때마다 그 결과(중요한 고리의 개수)를 한 줄에 하나씩, 주어진 순서대로 출력한다.