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
~P_1~, ~P_2~, ...~P_n~ mà ~P_1 = A~, ~P_n = B~ và có kết nối giữa ~P_k~ và ~P_{k - 1}~, ~k \in \{2, \dots 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 \rightarrow 5~ số nguyên với ý nghĩa như sau:
- 'D' ~N \rightarrow~ xác định số hành tinh là ~N~, ~N \le 6000000~, hành tinh đánh số từ ~1~ ...~N~.
- 'C' ~\rightarrow~ tạo kết nối giữa các cặp hành tinh.
- 'Q' ~\rightarrow~ 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$$1~ tạo ~3~ kết nối ~(1~, ~100)~, ~(1~, ~101)~, ~(1~, ~102)~.
- ~C~ ~1~ ~100~ ~3~ tạo ~3~ kết nối sau ~(1~, ~100)~, ~(1~, ~105)~, ~(1~, ~110)~.
- ~C~ ~1~ ~100~ ~5~ 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.
Sample Input 1
d 5
C 1 3
D 20
q 1 3
c 1 10 10
Q 1 2 18 1 1
Sample Output 1
0 1
9 9
Sample Input 2
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
Sample Output 2
1 0
0 5
5 0
Comments