[ACM 題目] 計畫巧遇

contents

1. 1. Description
   1. 1.1. Background
   2. 1.2. Problem
2. 2. Input
3. 3. Output
4. 4. Sample Input
5. 5. Sample Output
6. 6. Solution

Description

Background

正陷入暗戀的蘿莉控，對象正是那小海女 “能年犬”，為了與其相遇，做了一個情報偵測器，但總不能刻意繞道去相遇，這顯然會相當接近跟蹤狂。根據情報網顯示，地圖將會長得跟樹狀圖一樣，接著會有一連串的消息顯示小海女疑似出現的地方，同時也會被驗證是假消息。

蘿莉控只想知道如果從 x 點回到家的路上，有沒有機會遇到小海女。如果事先知道將會在哪個場所相遇，就能事先準備。接下來就請你協助他了！

Problem

給定一棵樹，樹根編號 0，每個點一開始的權重為 0，操作有以下兩種。

操作 M x : 將節點 x 的權重從 0->1 或者 1->0。
操作 S x : 輸出從 x 到 root 路徑上，第一個權重為 1 的節點編號。

Input

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

Output

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行。

Sample Input

10
0 1
0 2
1 3
0 4
3 5
4 6
5 7
5 8
4 9
10
M 1
S 8
S 4
M 0
M 7
M 9
S 5
M 3
M 8
S 5

31
0 1
0 2
0 3
1 4
1 5
2 6 
2 7
3 8
4 9
4 10
4 11
6 12
6 13
12 14
12 15
13 16
13 17
14 18
14 19
14 20
17 21
17 22
20 23
21 24
21 25
22 26
22 27
23 28
24 29
24 30
10
M 6
S 29
S 9
M 0
S 9
S 6
S 2
M 6
S 29
S 6

Sample Output

1
-1
1
3

6
-1
0
6
0
0
0

Solution