Hybrid Search

You are the proud owner of a newly built house in the Efficient Residences
complex, so effectively built that there are no redundant streets in it,
looking like a tree from higher up. Rumor has it that the constructor will start
connecting houses to the sewage network. You know in which order will the
constructor go through the houses. Since you want yours connected as soon
as possible, you count up a bribe to change a small part of the ordering
process in your favour.

You are given a tree with  nodes that is rooted in the node with index .
You are also given the index of a node , . We can do the
following types of tree searches:

itemize
    Start with a BFS from , and at some point change into a DFS
(possibly immediately in ). We don't necessarily have to change into DFS
during the search.
    Start with a DFS from , and at some point change into a BFS
(possibly immediately in ). We don't necessarily have to change into BFS
during the search.
itemize

After we change the search type (e.g. in node ), we will only visit the nodes
from 's subtree further on. We suppose that  was already visited in the
first search.

You must compute for each of the two types of hybrid searches what is the
smallest position in which the node with index  can appear.

The tree neighbours are considered in the Breadth/Depth-First Searches
in the order given in the input.
You can consult below the exact implementations we use for DFS and BFS:

algorithm[H]
Depth-First Search (DFS) / Breadth-First Search (BFS)

algorithmic
function traversal(, ):
     empty list gray
will contain the traversal nodes
     empty list gray behaves as either a stack or a queue,
depending on 

    append  to 

    while  is not empty:
         assign
and pop rightmost if  DFS else
leftmost from 
        append  to 

        for each  in
reversed() if  DFS
else : gray
we need to reverse to enforce the input ordering for DFS
            if   :
                append  to


traversal(,  DFS or
BFS)
algorithmic
algorithm

Input

The first line contains two numbers,  and  ().

The next  lines contain two numbers each,  and 
(). There is an edge in the tree between the nodes indexed
 and .

If  and  are children of  and the edge   (or  )
appears before the edge   (or  ) in the input, then  will appear
before  in any DFS or BFS from a node whose subtree contains .

Output

Write on the first line the smallest position in the hybrid search the node
indexed  may be found (counting from ), if we start with a BFS.

Write on the second line the analog if we start with a DFS.

Example Explanations

figure[!h]
        hybrid-search-ex1.pdf
    For the first example, if we start with BFS, it is optimal to
    switch to DFS in node ,  being the seventh visited node. If we
    switched in node  instead, we would have needed  positions instead.
    If we start with DFS, we could optimally change in either node  or node
    .
figure

figure[!h]
        hybrid-search-ex2.pdf
    For the second example, if we start with DFS, it is also possible
    to achieve  if we never change to BFS.
figure

figure[!h]
        hybrid-search-ex3.pdf
    For the third example, it doesn't matter with which search we
    begin, as both hybrid strategies have an optimal answer of . Note that if
    we instead only used one of the two basic searches, we would have gotten
    both times an answer of .
figure