在创意儿童游戏教室（ICPC）里有 $n$ 个孩子。随着时间的推移，一些孩子之间会成为朋友。友情是双向的，也就是说，如果孩子 A 是孩子 B 的朋友，那么孩子 B 也是孩子 A 的朋友。另一方面，友情不具有传递性。如果孩子 A 和孩子 B 是朋友，且孩子 B 和孩子 C 是朋友，孩子 A 和孩子 C 并不一定是朋友。由于新学年刚刚开始，目前还没有任何孩子之间是朋友。

如果一个孩子在教室里表现良好，老师有时会给这个孩子一个玩具。最初，所有孩子都没有任何玩具。ICPC 认为任何孩子的玩具数量都不应超过 50 个，因此如果给某个孩子玩具会使其玩具数量超过 50 个，则老师不允许给该孩子玩具。

有时，一个孩子会厌倦与自己的朋友玩玩具，并嫉妒其他拥有很多玩具的孩子。该孩子会想知道，在所有不是其朋友的其他孩子中，拥有的最大玩具数量是多少。

输入格式

第一行包含两个整数：孩子的数量 $n$ 和询问的数量 $q$（$1 \le n, q \le 4 \cdot 10^5$）。

孩子们从 $1$ 到 $n$ 进行编号。每个询问为以下格式之一：

• F i j — 表示孩子 $i$ 和孩子 $j$ 成为朋友。保证孩子 $i$ 和孩子 $j$ 此前不是朋友，且 $i \neq j$。
• A i — 表示老师给了孩子 $i$ 一个玩具。
• Q j — 表示孩子 $j$ 想要知道，在所有不是其朋友的其他孩子中，拥有的最大玩具数量是多少。

保证任何孩子拥有的玩具数量永远不会超过 50 个。

输出格式

对于每个格式为 Q j 的询问，输出一个整数 $k$，表示所有不是孩子 $j$ 朋友的其他孩子中，拥有的最大玩具数量。如果孩子 $j$ 与所有其他孩子都是朋友，则令 $k = -1$。

样例

输入样例 1

3 10
Q 1
A 2
A 1
A 2
Q 3
Q 2
F 2 3
Q 3
F 1 3
Q 3

输出样例 1

0
2
1
1
-1