스타게이트

오래전, 아주 먼 은하계에서 한 진보된 문명이 태양계 사이를 순간 이동하는 방법을 발견하고, 멀리 떨어진 행성들을 연결하는 스타게이트 쌍을 건설하기 시작했다. 그 연결망이 매우 복잡해져서 어떤 세계들이 서로 연결되어 있는지 관리하는 데 도움이 필요하게 되었다.

시스템들의 연결 정보를 관리하는 프로그램을 작성하여라. 두 행성 $A$와 $B$는, 둘 사이에 직접 연결된 스타게이트가 있거나, $P_1 = A$이고 $P_n = B$이며 모든 $k \in \{2, \ldots, n\}$에 대해 $P_{k-1}$과 $P_k$가 직접 연결되어 있는 행성 열 $P_1, P_2, \ldots, P_n$이 존재하면 '연결되어 있다'고 한다. 모든 연결은 양방향이며, 두 행성 사이에 여러 개의 경로가 있을 수 있다.

입력은 하나 이상의 데이터 집합으로 이루어지며, 빈 줄은 없다. 각 명령은 한 줄에 하나씩 주어지고, 대문자 또는 소문자 'D', 'C', 'Q' 중 한 글자로 시작한 뒤 $1$개에서 $5$개의 정수가 이어진다.

• 'D'(define)는 정수 $N$ ($N \le 6000000$) 하나를 받는다. $1$번부터 $N$번까지 번호가 매겨진 행성들로 이루어지고 연결이 하나도 없는 새로운 데이터 집합을 시작한다.
• 'C'(connect)는 하나 이상의 행성 쌍을 연결한다.
• 'Q'(query)는 하나 이상의 행성 쌍이 연결되어 있는지 묻는다.

'C'와 'Q' 명령(아래에서는 'X'로 표기)은 같은 인자 형식을 공유한다.

• X src dst — 한 쌍 $(src, dst)$.
• X src dst nnn — $nnn$개의 쌍 $(src, dst), (src, dst+1), \ldots, (src, dst+nnn-1)$. 예: X 1 100 3은 $(1,100), (1,101), (1,102)$를 뜻한다.
• X src dst nnn step — $i = 0, \ldots, nnn-1$에 대한 $nnn$개의 쌍 $(src, dst + i \cdot step)$. 예: X 1 100 3 5는 $(1,100), (1,105), (1,110)$을 뜻한다.
• X src dst nnn dststep srcstep — $i = 0, \ldots, nnn-1$에 대한 $nnn$개의 쌍 $(src + i \cdot srcstep, dst + i \cdot dststep)$. 예: X 1 100 3 5 15는 $(1,100), (16,105), (31,110)$을 뜻한다.

'C' 명령에서는 나열된 모든 쌍을 연결하고, 'Q' 명령에서는 나열된 모든 쌍을 검사한다. 참조되는 모든 행성 번호는 현재의 $N$에 대해 $1$과 $N$ 사이에 있다.

각 'Q'(query) 명령마다 한 줄씩, 입력 순서대로 출력한다. 각 줄에는 두 정수를 세 글자 ' - '(공백, 붙임표, 공백)로 구분하여 출력하는데, 먼저 그 질의에서 연결된 쌍의 개수를, 그다음 연결되지 않은 쌍의 개수를 출력한다. 뒤따르는 공백은 출력하지 않는다.