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.

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}$`

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.

Input | Output |
---|---|

9 13 1 2 1 3 2 4 2 5 3 6 3 7 4 8 2 9 Answer Add 1 8 Answer Add 5 4 Answer Add 2 9 Answer Add 8 7 Answer Add 4 8 Answer Remove 9 2 Answer | 0 0 4 1 2 2 1 3 1 4 2 4 1 4 |