Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Path Intersection Extended

By Peregrine_Falcon · Limits 1s, 256 MB

Do you remember the problem from ICPC Dhaka Regional 2018 named PathPath IntersectionIntersection by Md. Imran Bin Azad? This is an extended version of that problem.

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

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

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

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

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

Input

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

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

Following next QQ lines consists of one of three types of queries in the following format:

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

Output

For each of the AnswerAnswer type queries, you've to print XX and KK in one line separated by a single space. The total number of nodes part of KK paths from the set of paths and the maximized value KK. If the set is empty, just print 00 00 instead.

Sample

InputOutput
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

Discussion

Statistics


100% Solution Ratio

BigBagEarliest, 3w ago

serotoninFastest, 0.3s

serotoninLightest, 20 MB

serotoninShortest, 2309B

Submit

Login to submit

Editorial

This problem can be solved using HeavyHeavyHeavy LightLightLight DecompositionDecompositionDecomposi...

Related Contests