Problem 3425 --韭菜国的大选

3425: 韭菜国的大选

上一题 正确率: $87.50\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $8$ 正确数量 $7$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

韭菜国的大选年到了，韭菜国议会将要选举出新的执政党。议会的选举制度是这样的：最一开始的时候每位议员都会各自组建独立党派，每个党派之间可以派出一位代表进行一对一谈判，如果谈判成功，那么两位议员分属的不同党派将合并成一个新的党派。最后包含议员数量最多的党派将获胜。作为韭约时报的记者，你将全程报道大选的过程。每一次的一对一谈判将是你报道的重点，此外，你还需要回复你热情的观众：选民们有时会对一些高人气的议员的活动很感兴趣，比如某两位议员现在是否属于同一党派，如果是，那么他们是什么时候成为同一阵营的。现在只考虑成功的谈判，并把每一次成功的谈判和观众的提问都视为一次事件，在大选中有若干次事件发生，对每次提问的事件，你都需要进行回答。

Input

第一行两个正整数 n和 m，分别表示韭菜国议会有 n 名议员，选举中发生了 m个事件。保证 n<=3*10^5, m <= 3 * 10^5。
接下来 m 行，每行一个字符串 s 和两个整数 a, b。保证 1<=a,b<=n。
如果 s的内容为`join`，则意味着本次事件是 a和 b 两位议员成功进行了谈判。
如果 s 的内容为`query`，则意味着你需要回答当前 a 和 b两位议员是否属于同一党派。

Output

对于每一次询问的事件，你都需要进行回答，每次回答占一行，如果两位议员不是同一阵营，输出NO；反之输出YES和一个数字 $i$，表示是在第 $i$ 次事件中两位议员成为了同一阵营。

Sample Input复制

5 8
join 1 3
query 2 5
join 3 5
join 1 4
query 1 5
query 4 3
join 2 4
query 2 5

Sample Output复制

NO
YES 3
YES 4
YES 7

推荐代码 查看3425 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$0 $ms] 滁院の亚托克文 613372 2020-09-28 20:57:09
内存最少[$4428 $KB] fancy 742793 2021-04-22 22:12:38
第一AC AOJ大管家 613354 2020-09-28 19:06:14
第一挑战 AOJ大管家 613354 2020-09-28 19:06:14

赛题来源/所属竞赛 2020安徽省ACM赛9月月赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1539 2020安徽省ACM赛9月月赛 2020-09-27 13:00:00 请登录