Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Stargates
Time Limit: 3000MSMemory Limit: 65536K
Total Submissions: 2418Accepted: 545

Description

"A Long Time Ago, in a Galaxy Far, Far Away..." one advanced civilization discovered a manner of instant traveling between solar systems. Since that moment, they have devoted all their efforts to constructing pairs of stargates that connect distant planets. Soon enough communication network became so complex that they require help to maintain information about the connected worlds.

Write a program that will help them maintain information about the connected systems and we will make sure that the best of your solutions will be forwarded to their space-time continuum. Planets A and B are connected if there is a direct stargate connection between them, or there is a planetsequence P1, P2,..Pn where P1=A, Pn=B and there is a direct stargate connection between Pk and Pk-1, k Î{2..n} . Connections are bidirectional. There can be multiple connection paths between two planets.

Input

Input file consist of multiple data sets. Each data set occupies one or more lines. There are no empty lines in the input file. Each line starts with a single letter 'D', 'C' or 'Q' (upper or lower case) followed by 1 to 5 integers with following meaning:
'D' (define) has only one argument which defines number of planets N considered in following data set (N<=6000000, planets are numerated from 1..N).
'C' (connect) creates a connection between a given pair(s) of planets.
'Q' (query) examines if a given pair(s) of planets are connected.
Both 'C' and 'Q' command ('X' in following text) share the same syntax:
X src dst – Creates a connection (or query) between given pair of planets (src, dst).
X src dst nnn – Creates a connection (or query) between src planet and nnn consecutive planets numerated from dst.
Example: X 1 100 3 creates following links (1,100), (1,101), (1,102).
X src dst nnn step – Creates a connection (or query) between src planet and nnn planets numerated from dst with given step.
Example: X 1 100 3 5 creates following links (1,100), (1,105), (1,110).
X src dst nnn dststep srcstep – Creates a connection (or query) between nnn pairs of planets numerated from src with srcstep and dst with dststep respectively.
Example: X 1 100 3 5 15 creates following links (1,100), (16,105), (31,110).

Output

Output file contains one line pre each query ('Q') line in the input file. Each line contains two numbers separated by space dash space sequence. First value represents number of connected planet pairs from appropriate query while second represents number of disconnected planet pairs.

Sample Input

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

Sample Output

0 - 1
9 - 9

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator