编程介的小学生 2017-04-10 10:21 采纳率: 20.5%
浏览 728
已采纳

Stargates

"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 planet sequence P1, P2,..Pn where P1=A, Pn=B and there is a direct stargate connection between Pk and Pk-1, (2<=k<=n). Connections are bidirectional. There can be multiple connection paths between two planets.

Input

Input 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

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-04-27 06:20
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误