TopCoder

Thumb a

User's AC Ratio

91.7% (44/48)

Submission's AC Ratio

45.8% (66/144)

Description

你,妹可,成功了喚醒了冷凍艙(詳情請見Problem A)中沉睡的人-一隻小蘿莉。

「...盯...」
「疑?是一隻小蘿莉耶!」
「...盯...盯...」
「...不要用那種眼神一直盯著我看嘛~」
「...盯~...」
「啊啊啊啊啊啊為什麼這樣我還會覺得有快感啊啊啊啊(以下依照國家規記予以和諧處理)。」

「所以你也不知道你為甚麼會在這裡嗎?」恢復正經的妹可問到。
小蘿莉只是點點頭,經由妹可驚人的推理(DP)能力,他已經知道小蘿莉的名字叫做夏梨(Natsunashi)。
「看來我們必須好好調查一下了...疑?!」你轉頭一看,發現你們被蘿莉機器人包圍了!
「啊啊,快跑啊!」妹可拉起了夏梨的手,跑了起來。

妹可衝出了房間,在走廊上狂奔 順便享受得來不"義"的小確幸 ,身後那些長的很像夏梨的蘿莉機器人不斷的追來。
跑跑停停、躲躲藏藏經過幾個小時,同時妹可不忘邊跑邊用驚人的推理(DP)能力,發現周圍的牆上,掛滿了硬佛石株式會社歷代社長的肖像。
突然,你停在第27屆社長的肖像前。

「喔膩醬!你怎麼停下來了!她們快要追來了啦!」夏梨害怕的難得跟妹可說話了,但是妹可卻只是靜靜的看著牆上刻的文字。
「我有辦法了!」你運用了你驚人的推理(DP)能力,發現了一個驚人的事實。

這群蘿莉機器人是由一個到數個的主控者來控制,稱為"女王"。每個蘿利機器人都隸屬於一位女王(除非她是女王),而根據這樣的主從關係,蘿莉機器人被分成好幾個"部隊",而根據觀察,主控系統會在適當的時機將兩個部隊合併,這時被合併的部隊裡的所有蘿莉機器人(包括女王)都會服從同一個女王。因此只要知道女王是誰,就可以收服整個蘿莉機器人部隊了!

「而那個總主控者...就是妳!夏梨!」
「疑!!可是...可是...」
「別擔心,第一次可能會有點辛苦,但是多試幾次就可以很輕鬆的進進出出了!」
「可是...可是...我還沒有心理準備...」
「沒有時間了!能夠進入蘿莉機器人的主控系統裡的人就只有妳了!夏梨!」

『想歪什麼的最討厭了。』---妹可。

Input Format

第一行有兩個個整數N、Q分別代表有N隻蘿莉機器人(編號1~N)和有Q個事件。
接下來Q行以一個字串S開頭代表事件種類,
如果S是"Masuta"(不含引號),接下來有兩個整數A、B,代表夏梨接收到的訊息,也就是編號B的蘿莉機器人隸屬的部隊被併入編號A的蘿莉機器人所在的部隊,編號A的蘿莉機器人隸屬的女王成為這個新部隊的女王。
如果S是"Kuiin"(不含引號),接下來有一個整數X。

因為主控電腦已經放了看起來至少500年了, 連4個管理者去修都修不好 ,有時候他也可能會下達將同一個部隊合併的命令喔。

對於33%的測資,滿足N≤1000,Q≤1000。
對於100%的測資,滿足N≤100000,Q≤200000,1≤A,B,X≤N。

Output Format

對於每個Kuiin事件,告訴夏梨編號X的蘿莉機器人的女王是誰,好讓她可以早點擺平這群小蘿莉。

Sample Input

10 10
Masuta 2 6
Kuiin 3
Masuta 6 9
Kuiin 6
Masuta 7 4
Kuiin 3
Masuta 9 6
Kuiin 4
Masuta 6 4
Kuiin 7

Sample Output

3
2
3
7
2

Hints

一開始每隻小蘿莉的女王都是自己呦~。

Problem Source

資訊社 28屆C/C++學術考試 by果茶

Subtasks

For Testdata: 0 ~ 2, Score: 33
For Testdata: 3 ~ 8, Score: 67
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536