Roger and Tree III

All submissions for this problem are available.
Roger was able to solve his problem based on tree last time, only because of your help. He has been doing good and is learning and practicing various problems on trees (as he likes solving problems on connected undirected acyclic graphs). This time he is stuck with a harder problem and has spent almost a week trying to solve this problem, with no efficient solution till now. But, he has you as his friend and he knows that only you can help him with your excellent programming skills.
You will be given an input in the form of a growing tree. That is, initially you have a tree consisting only of vertex 1. At each step the tree will grow. So next, vertex u will be connected to vertex 1, then vertex v will be connected to either vertex 1 or vertex u, and so on till you get a tree consisting of 'N' vertex. However, at any instant while adding the vertexes you will be given a vertex 'x' (which is already present in the tree grown so far), and you will be asked to print the eccentricity of the given vertex x.
Let G be a graph and 'x' be a vertex of G.
The eccentricity of the vertex 'x' is the maximum distance from 'x' to any vertex present in G.
That is, e (x) = max {d (x, y) : y is in G}.
Of Course vertex y, should also be present in the tree, grown so far.
Along with the eccentricity, you should also print the vertex 'y'.
Please help Roger.
Input
First line contains 'N' and 'M', where N = Number of nodes in the tree and M = Number of Queries.
Next M lines will either have an input of the type "U x y" or "Q x".
For the input of type "U x y", you have to connect the vertex 'y' to the vertex 'x', where vertex 'x' is already present in the tree and vertex 'y' is the new vertex. Obviously there will be (N  1) inputs of the type "U x y".
Output
For each input of the type "Q x", you have to print the eccentricity of vertex 'x', followed by the vertex 'y'.
If there are multiple such 'y'. Print the smallest 'y'.
Constraints
1 ≤ N ≤ 10^5
N  1 ≤ M ≤ 2*N
1 ≤ x, y ≤ N
Example
Input
5 8
Q 1
U 1 4
Q 1
U 4 2
U 1 5
U 5 3
Q 1
Q 2
Output
0 1
1 4
2 2
4 3
Explanation
Initially the tree has vertex 1.
Q 1 => Eccentricity of vertex 1 is 0.
U 1 4 => Connect vertex 4 to vertex 1.
Q 1 => Eccentricity of vertex 1 is 1.
U 4 2 => Connect vertex 2 to vertex 4.
U 1 5 => Connect vertex 5 to vertex 1.
U 5 3 => Connect vertex 3 to vertex 5.
Q 1 => Eccentricity of vertex 1 is 2. Vertex 2 and Vertex 3 both are at a distance of 2 from vertex 1. Print the smaller one.
Q 2 => Eccentricity of vertex 2 is 4.
Author:  harshitasia 
Tags  harshitasia 
Date Added:  27022015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 