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.

CLICK HERE TO DOWNLOAD

March Long Challenge 2021 Solutions

An Interesting Sequence ISS SOLUTION
Tree House THOUSES SOLUTION
Valid Paths VPATH SOLUTION
Modular Equation MODEQ SOLUTION
Tic Tac Toe TCTCTOE SOLUTION
Xor Equality XOREQUAL SOLUTION
Golf LKDNGOLF SOLUTION
Solubility SOLBLTY SOLUTION

April Long Challenge 2021 Solutions

Chef and Dice SDICE Solution
Worthy Matrix KAVGMAT Solution
Binary String MEX MEXSTR Solution
Boolean Game BOOLGAME Solution
Tree Permutations TREEPERM Solution
Destroy the EMP Chip CHAOSEMP Solution
Chef and Pair Flips PAIRFLIP Solution
String Power STRPOW Solution
Brahma and Shiva SHRINES Solution
Water Sort Puzzle (Challenge) WTRSORT Solution
World Record BOLT Solution
Strong Language SSCRIPT Solution
Valid Pair SOCKS1 Solution

Naruto and One Shot SOLUTIONS ECAUG207