# Naruto and One Shot SOLUTIONS ECAUG207

Page Contents

### Naruto and One Shot SOLUTIONS ECAUG207

There are N towns numbered 1 to N. The towns are associated through bi-directional ways in the middle of them. The entire system is as a tree.

Every town has just 1 warrior however they help each other in the midst of emergency by sending their contender to the town in peril through ways along the towns. Crushing a contender will mean overcoming his town. Specifically, If town X is enduring an onslaught, all towns having a way to X will send their warriors for help.

Naruto needs to overcome all the towns. However, he can’t take on endless contenders simultaneously so he intends to utilize a mystery procedure with which he can demolish any 1 town (alongside ways associated with it) in a split second. In any case, it tends to be utilized just a single time. He understood that in the event that he crushes any town, state X, the greatest number of warriors he needs to battle without a moment’s delay lessens to W. He needs W to be as little as could reasonably be expected. Assist him with finding the ideal X.

If there should be an occurrence of numerous answers, pick the littlest estimation of X.

Info:

First line will contain T, number of testcases. At that point the testcases follow.

First Line contains N.

Next N−1 lines contain U,V, signifying a way between town U and V.

Yield:

For each Test case, print in another line, ideal X and relating estimation of W.

Limitations

1≤T≤10

3≤N≤105

1≤U,V≤N

U!=V

Test Input:

1 2

1 3

2 4

3 5

1 2

2 3

Test Output:

1 2

2 1

Clarification:

Test 1: By pulverizing town 1, The contenders Naruto will be battling simultaneously will be from towns [2,4] and [3,5]. For this W = 2. No other decision can give lesser W. Henceforth 1 is ideal decision.