Problem Description

There are $n$ children in the Imaginative Child's Play Classroom (ICPC). Friendships are bidirectional but not transitive. At the beginning of the school year, no two children are friends.

Teachers sometimes give toys to well-behaved children. Initially, no child has any toys. No child may ever receive more than $50$ toys.

At times, a child wants to know the maximum number of toys owned by any other child who is not their friend. Process friendship, toy, and query events as they occur.

Input Format

The first line contains two integers $n$ and $q$ ($1\le n,q\le4\cdot10^5$), the number of children and the number of events. Children are numbered $1$ through $n$.

Each of the next $q$ lines has one of the following forms:

• F i j: children $i$ and $j$ become friends. They were not already friends, and $i\ne j$.
• A i: child $i$ receives one toy.
• Q j: child $j$ asks for the maximum number of toys owned by another child who is not their friend.

No child will ever have more than $50$ toys.

Output Format

For every Q j event, output the requested maximum. If child $j$ is friends with every other child, output $-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

0
2
1
1
-1