# Path Intersection Extended

Limits 1s, 256 MB

Do you remember the problem from ICPC Dhaka Regional 2018 named `\$Path\$` `\$Intersection\$` by Md. Imran Bin Azad? This is an extended version of that problem.

You're given an unweighted tree consist of `\$N\$` nodes and `\$N-1\$` edges. Every pair of nodes have a unique simple path between them.

You've to perform `\$Q\$` queries on this tree. There can be three different types of queries. Initially, you've an empty set of paths.

• `\$\texttt{Add A B}\$`:
Add a path between node `\$A\$` and `\$B\$` in the set of paths. You'll not be given a path that already exists in the set of paths.

• `\$\texttt{Remove A B}\$`:
Here you'll be given a path between node `\$A\$` and `\$B\$` that exists in the set of paths. You've to remove that path from the set of paths.

• `\$\texttt{Answer}\$`:
Find the total number of nodes which are part of exactly `\$K\$` paths from the set of paths and the value of `\$K\$` is maximized. If the set is empty, just print 0 0.

## Input

The first line of input consists of two integers `\$N\$` and `\$Q\$` `\$( 3 ≤ N, Q ≤ 10^5)\$` number of nodes in the tree and the number of queries to perform respectively.

Each of the next `\$N-1\$` lines consists of two integers `\$U\$` and `\$V\$` `\$(1 ≤ U,V ≤ N, U\neq V)\$` denoting there is an edge between node `\$U\$` and `\$V\$`.

Following next `\$Q\$` lines consists of one of three types of queries in the following format:

• `\$\texttt{Add A B}\$` `\$(1 ≤ A, B ≤ N, A\neq B)\$`
• `\$\texttt{Remove A B}\$` `\$(1 ≤ A, B ≤ N, A \neq B)\$`
• `\$\texttt{Answer}\$`

## Output

For each of the `\$Answer\$` type queries, you've to print `\$X\$` and `\$K\$` in one line separated by a single space. The total number of nodes part of `\$K\$` paths from the set of paths and the maximized value `\$K\$`. If the set is empty, just print `\$0\$` `\$0\$` instead.

InputOutput
```9 13
1 2
1 3
2 4
2 5
3 6
3 7
4 8
2 9
```0 0