你知道GATE嗎? 知道為什麼GATE世界裡人們為何露出笑容嗎?
不知道沒關係,因為你已經立志要守護人們的笑容了。
你,初等魔法師見習生,生活在一個最近被地球人發現的異世界裡。
這是個有著精靈和亞神的神祕異世界,而自衛隊的二等陸衛—伊丹,最近被指派負責調查這裡的人們的生活還有風俗民情。而你的老師,藍色魔法少女,和其他異世界人一起負責協助他。
又到了巡邏的日子,今天,你也決定守護著大家的笑容。
「這個笑容由我來守護!」你這樣說。
「這個笑容由我來守護!!!!」
「這個笑容由我來守護!!!!!!!」
「這個笑容由我來守護!!!!!!!!!!」
「這個笑容由我來守護!!!!!!!!!!!!!」
「這個笑容由我來守護!!!!!!!!!!!!!!!!」
「這個笑容由我來守護!!!!!!!!!!!!!!!!!!!」
你今天也守護了大家的笑容。
我們都知道,要守護笑容不容易,在異世界生活也不容易。
在異世界想要生存下去,必須努力的去工作、練習、交涉。在這些人尋求生存的過程中,總有些時候利益會衝突,當所有人都想要爭取同樣的東西,比如權利、財富、或是另一半,可能只有一個人能夠得到,最後能露出笑容的可能也只有一個人。
伊丹身為第三偵察隊的隊長,他希望可以知道,在可能存在利益衝突的情況下,能露出笑容的有多少人。
假設只要沒有人和你有相同的目標,那你最後你一定可以露出笑容(當然我們知道,現實中有人就算沒人跟你搶你可能還是會失敗QQ)。如果有兩個以上的人目標相同,那這群人中只有一個人最後會露出笑容。
伊丹會在異世界的各地進行深入的調查,如果他發現了兩個人有相同的目標,他會將之紀錄起來,當然他也可能會修正他的紀錄,而他想知道最後能有幾個人會露出笑容,才能派你才能去守護他們。
伊丹的紀錄中,會有很多由兩個數字組成的紀錄,代表某個人和某個人的目標相同。
接著伊丹會進行調查,他可能會增加或刪去某個紀錄。
注意,刪去或是沒有紀錄不代表目標不相同,只是不確定而已,伊丹當然可以透過推理來得知實際狀況。當A跟B目標相同,B跟C目標也相同時,我們可以當作A跟C目標也是相同的。如果現在把B跟C相同的紀錄刪去,那除非有其他紀錄可以推測出A和C相同,不然你就可以當作AB和C目標是不同的,不會衝突。
現在伊丹給你一些紀錄。
他想在每次加入或刪除紀錄時,得知現在可以露出笑容的人數,不過一直算真的很累人,還好他養了一隻藍色魔法少女,於是他決定找她幫忙寫個魔法幫他,但是你也知道,因為你,初等魔法師見習生,為了幫助你的老師,藍色魔法少女露出笑容,你只好讓她還有其他人開著車去野外露營,自己則留在基地編寫魔法函式。
「誰,可以守護我的笑容呢?........」
第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 的紀錄。
25%,$ N \leq 10; M+Q \leq 100 $
25%,$ N \leq 100; M+Q \leq 1000 $
50%,$ N \leq 500; M+Q \leq 5 \times 10^ 5 $
100%,$ 0 \leq A_i, B_i \leq N-1 ,A_i \ne B_i $。
對於每筆測資的Q筆修改,每次修改完請你輸出一行,代表當時能夠露出笑容的人數。
對於第二筆測資,一開始有 0 1, 1 2, 2 1,三筆紀錄,第一次刪除了2 1這筆紀錄,剩下 0 1, 1 2,會露出笑容的還是只有1個人,之後陸續刪除0 1,2 1,所以露出笑容的人數依序變成2、3。
Gate:果茶
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 25 |
2 | 1 | 25 |
3 | 2~3 | 50 |