TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

80.2% (65/81)

Submission's AC Ratio

23.6% (214/905)

Tags

Description

你知道GATE嗎? 知道為什麼GATE世界裡人們為何露出笑容嗎?
不知道沒關係,因為你已經立志要守護人們的笑容了。

你,初等魔法師見習生,生活在一個最近被地球人發現的異世界裡。
這是個有著精靈和亞神的神祕異世界,而自衛隊的二等陸衛—伊丹,最近被指派負責調查這裡的人們的生活還有風俗民情。而你的老師,藍色魔法少女,和其他異世界人一起負責協助他。

又到了巡邏的日子,今天,你也決定守護著大家的笑容。

「這個笑容由我來守護!」你這樣說。

「這個笑容由我來守護!!!!」

「這個笑容由我來守護!!!!!!!」

「這個笑容由我來守護!!!!!!!!!!」

「這個笑容由我來守護!!!!!!!!!!!!!」

「這個笑容由我來守護!!!!!!!!!!!!!!!!」

「這個笑容由我來守護!!!!!!!!!!!!!!!!!!!」

你今天也守護了大家的笑容。

我們都知道,要守護笑容不容易,在異世界生活也不容易。
在異世界想要生存下去,必須努力的去工作、練習、交涉。在這些人尋求生存的過程中,總有些時候利益會衝突,當所有人都想要爭取同樣的東西,比如權利、財富、或是另一半,可能只有一個人能夠得到,最後能露出笑容的可能也只有一個人。

伊丹身為第三偵察隊的隊長,他希望可以知道,在可能存在利益衝突的情況下,能露出笑容的有多少人。
假設只要沒有人和你有相同的目標,那你最後你一定可以露出笑容(當然我們知道,現實中有人就算沒人跟你搶你可能還是會失敗QQ)。如果有兩個以上的人目標相同,那這群人中只有一個人最後會露出笑容。
伊丹會在異世界的各地進行深入的調查,如果他發現了兩個人有相同的目標,他會將之紀錄起來,當然他也可能會修正他的紀錄,而他想知道最後能有幾個人會露出笑容,才能派你才能去守護他們。

伊丹的紀錄中,會有很多由兩個數字組成的紀錄,代表某個人和某個人的目標相同。
接著伊丹會進行調查,他可能會增加或刪去某個紀錄。
注意,刪去或是沒有紀錄不代表目標不相同,只是不確定而已,伊丹當然可以透過推理來得知實際狀況。當A跟B目標相同,B跟C目標也相同時,我們可以當作A跟C目標也是相同的。如果現在把B跟C相同的紀錄刪去,那除非有其他紀錄可以推測出A和C相同,不然你就可以當作AB和C目標是不同的,不會衝突。

現在伊丹給你一些紀錄。
他想在每次加入或刪除紀錄時,得知現在可以露出笑容的人數,不過一直算真的很累人,還好他養了一隻藍色魔法少女,於是他決定找她幫忙寫個魔法幫他,但是你也知道,因為你,初等魔法師見習生,為了幫助你的老師,藍色魔法少女露出笑容,你只好讓她還有其他人開著車去野外露營,自己則留在基地編寫魔法函式。

「誰,可以守護我的笑容呢?........」

Input Format

第1行有1個數字T,代表測資筆數。
每筆測資第1行有3個整數N、M、Q。
接下來M行每行兩個整數Ai、Bi,代表Ai和Bi這兩個人目標相同。
接下來Q行,每行有一個字元 c 和兩個整數Ai、Bi,代表修改一個紀錄。
如果 c 是 N,代表增加一筆 Ai、Bi 兩人目標相同的紀錄;如果 c 是 D,代表要刪除一筆 Ai、Bi 目標相同的紀錄,你可以當作所有刪除都是合法的。
可能會出現兩筆以上相同的紀錄,但是不會出現 Ai == Bi 的紀錄。

100%,$ N \leq 5 \times 10^ 5; M+Q \leq 5 \times 10^ 5, 0 \leq Ai, Bi \leq N-1 ,Ai \neq Bi $。

Output Format

對於每筆測資的Q筆修改,每次修改完請你輸出一行,代表當時能夠露出笑容的人數。

Sample Input 1

2
3 0 3
N 0 1
N 1 2
N 2 1
3 3 3
0 1
1 2
2 1
D 2 1
D 0 1
D 2 1

Sample Output 1

2
1
1
1
2
3

Hints

這題和原版的範圍不太一樣喔!

Problem Source

果茶,多多。

Subtasks

No. Testdata Range Score
1 0~10 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 262144 1
1 3000 262144 262144 1
2 3000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1500 262144 262144 1
6 3000 262144 262144 1
7 3000 262144 262144 1
8 3000 262144 262144 1
9 3000 262144 262144 1
10 3000 262144 262144 1