蝈蝈的帝国之争

TimeLimit:1000MS  MemoryLimit:64MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

已知ACM大陆上有 n 个国家,并且这些国家会组成联盟。一个国家只能附属于一个联盟。初始时各个国家“自成一体”,不存在任何联盟关系。

各个国家会因为战略而发生以下事件:

1、国家A和国家B组成一个新的联盟,如果这两个国家原本就附属于一个联盟,则会从原来的联盟中脱离

2、国家A加入国家B所属的联盟,如果国家A原本就附属于一个联盟,则会从原来的联盟中脱离,保证国家B附属于一个联盟

3、国家A脱离原来的联盟,回到最初“自成一体”的状态,保证国家A附属于一个联盟

作为军事战略家的你们,需要在各个事件发生的前后判断以下的问题:

1、判断国家A和国家B是否均附属于一个联盟并且附属于同一个联盟

2、判断当前环境中有多少联盟

3、判断国家A附属的联盟中有多少国家,如果国家A是“自成一体”的,则输出0

注:

1、如果一个联盟中所有的国家都脱离,则这个联盟不存在

2、就算一个联盟中只有一个国家,也是一个联盟,这个国家也附属于这个联盟,和“自成一体”状态不同

Input

第一行两个整数n,m,分别表示国家的数量、事件&问题的次数(2 ≤ n ≤ 100000,1 ≤ m ≤ 100000)

接下来m行,每行是以下某一种格式:

1、Union A B,表示事件1,A和B是两个整数,对应事件1中的A和B(1 ≤ A、B ≤ n,A ≠ B)

2、Join A B,表示事件2,A和B是两个整数,对应事件2中的A和B(1 ≤ A、B ≤ n,A ≠ B)

3、Separate A,表示事件3,A是一个整数,对应事件3中的A(1 ≤ A ≤ n)

4、Judge A B,表示问题1,输出“YES”或“NO”,A和B是两个整数,对应问题1中的A和B(1 ≤ A、B ≤ n,A ≠ B)

5、NumberOfAlliances,表示问题2,输出一个整数

6、NumberOfCountries A,表示问题3,输出一个整数,A是一个整数,对应问题3中的A(1 ≤ A ≤ n)

Output

对每一次提问的问题输出一行一个对应的答案

SampleInput
4 7
Union 1 2
Judge 1 2
Join 3 1
NumberOfCountries 1
Union 1 4
NumberOfAlliances
NumberOfCountries 3
SampleOutput
YES
3
2
2
Submit
题目统计信息详细
总AC数12
通过人数11
尝试人数14
总提交量33
AC率33.33%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: