56. 怎麼可能會後悔

0 Judge

Code: 0


怎麼可能會後悔

題目敘述

目睹了學姊的慘劇後,Madoka Kaname與Sayaka Miki心理遭受極大的創傷,雖然在Homura Akemi冷酷卻沉穩的開導下,讓他們稍微釋懷了點,但這段回憶將永遠無法忘懷。Sayaka Miki獨自走在放學的路上,想去探望生病躺握在醫院$Kyosuke Kamijo,他是Sayaka Miki的青梅竹馬,自從他的手受到車禍重創後無法繼續拉小提琴就鬱鬱寡歡的。如果已經沒有學姊來守護這個地方,這份工作要由誰繼續承擔?他是否有機會改變這個世界?心意已決的Sayaka Miki往她心中的理想向前奔去,不完成就要後悔一輩子了。

而Madoka Kaname留的比較晚,Homura Akemi也藉此把魔法少女以生命與不可逆的命運作為賭注的殘酷面告訴了Madoka Kaname,希望她不要誤入歧途。回家途中,有一群神色怪異的人群從她面前走過,這些人似乎是中了魔女的詛咒!不論她如何的呼喚也得不到任何的回應。十分有正義感的Madoka Kaname雖然什麼也幫不上,但也跟上前去試圖找出這群人的目的。走了不知多久,大家聚集到了一間十分巨大的工廠,而地上堆滿數罐不知從何而來的化學藥品,難不成魔女要讓這些人集體自殺?這真的太邪惡了,Madoka Kaname衝上前去把能拿到的所有東西瓶罐都丟出了窗外要阻止這一切,但此舉也驚動了潛伏於其中的魔女,讓Madoka Kaname陷入了詭異的結界。

sprout

魔女的結界由數個獨立的平台組成,隨著時間的變化而有所改變,平台間會突然地伸出一個通道與另一的平台連接在一起,似乎是在製作某種結界,好奇的Madoka Kaname即使身陷危險也要記錄著他所見到的一切!由於不知道什麼時候結界會完成,每隔一段時間Madoka Kaname會想要知道某個平台已經與幾個平台彼此可以互相抵達,這數量可以被定義為這些平台組成的結界大小!不過這計算非常的麻煩,不小心在遠方默默關注這一切的你,能夠還原Madoka Kaname的計算嗎?我們假設Madoka Kaname的計算都是正確無誤的。

突然間,有個人影飛越了近來與魔女戰鬥,熟悉的身形不是Sayaka Miki!?

輸入說明

測資的第一行有一個數字$T$,表示有$T$次獨立的紀錄,由於不知道哪份是Madoka Kaname的,所以你每一份都要認真的算。

每份資料第一行有兩個數字$N,Q$,魔女的結界創造了$N$個平台,編後依序由$1$到$N$,而Madoka Kaname依序做了$Q$次的紀錄,每一個紀錄有下三種型式:

  • $M~a~b$ 表示這時編號$a$與編號$b$的平台出現了一條路連接,也有可能出現自己連到自己成為環狀路的情況。
  • $C~x$ 表示$Madoka Kaname$想知道編號$C$平台處在的結界大小為何。
  • $Q~a~b$ 表示$Madoka Kaname$想知道編號$a$與編號$b$的平台是否處在同一個結界裡,是就回答$YES$,否則回答$NO$。

保證:$N \leq 10^5$,$Q \leq 4 \times 10^5$,由於記錄檔十分的巨大,你需要小心讀取資料的時間。

輸出說明

對於第$i$次獨立的紀錄要輸出一個$Case i:$來加以區隔,接下來對於每個Madoka Kaname想知道的詢問輸出一行,為Madoka Kaname計算的正確答案會是多少。

範例輸入

2
3 4
C 1
M 1 2
C 1
Q 2 3
4 7
M 1 2
M 2 3
M 3 1
C 2
Q 4 3
M 1 4
Q 2 4

範例輸出

Case 1:
1
2
NO
Case 2:
3
NO
YES

Judge Setting

run-time limit: 1000 ms
memory limit: 655360 byte
測資數量: 0