Giải bài trực tuyến

Bài này bạn cần quản lý thông tin kết nối giữa các hành tinh.

Hành tinh A, B được kết nối nếu chúng có đường đi trực tiếp hoặc có 1 dãy các hành tinh

P1, P2,..Pn mà P1=A, Pn=B và có kết nối giữa Pk và Pk-1, k ∈ {2,..n}.

Kết nối là 2 chiều và có thể có nhiều kết nối giữa 2 thành phố.

Input

Gồm nhiều test, mỗi test vài dòng, mỗi dòng bắt đầu bằng ‘D’, ‘C’ hoặc ‘Q’ (chữ hoa hoặc

thường) sau đó là 1 -> 5 số nguyên với ý nghĩa như sau:

• ‘D’ N -> xác định số hành tinh là N, N<=6000000, hành tinh đánh số từ 1..N.
• ‘C’ -> tạo kết nối giữa các cặp hành tinh.
• ‘Q’ -> kiểm tra các cặp hành tinh có kết nối.

Lệnh C và Q có cùng định dạng như sau (kí hiệu là chữ X )

X src dst – Tạo/truy vấn kết nối giữa 2 hành tinh src và dst

X src dst nnn – Tạo/truy vấn kết nối giữa hành tinh src và nnn hành tinh liên tiếp từ dst

VD: C 1 100 3 tạo 3 kết nối (1,100), (1,101), (1,102).

X src dst nnn step – Tạo/truy vấn kết nối giữa hành tinh src và nnn hành tinh bắt đầu từ

dst với bước nhảy là step.

VD: C 1 100 3 tạo 3 kết nối sau (1,100), (1,105), (1,110).

X src dst nnn dststep srcstep – Tạo/truy vấn kết nối giữa nnn cặp thành phố từ src với

bước nhảy là srcstep tại src và tới dst với bước nhảy là dststep.

VD: C 1 100 3 5 15 tạo 3 kết nối (1,100), (16,105), (31,110).

Output

Với mỗi truy vấn ‘Q’ in ra 2 số: số đầu tiên là số cặp thành phố kết nối, số thứ hai là số cặp thành phố không kết nối trong truy vấn tương ứng.

Input:
d 5
C 1 3
D 20
q 1 3
c 1 10 10
Q 1 2 18 1 1

Output:
0 1
9 9

Input:
d 5
d 1
q 1 1
d 10
q 1 6 5 1 1
c 1 2 9
q 1 6 5 1 1

Output:
1 0
0 5
5 0