S93-CA2-1

Time Limit: 1 Second    Memory Limit: 65536 KB

Oblivion

در حالی که بتمن با راس‌الغول مبارزه می‌کند، متوجه می‌شود که کمیسر گوردون و تعدادی از افسران GCPD توسط اسکیرکرو گروگان گرفته‌ شده‌اند. با توجه به این که بتمن نمی‌تواند این مبارزه را رها کند به نایت‌وینگ و رابین می‌گوید تا کمیسر گوردون و ماموران وی را نجات دهند. بتمن می‌داند آن‌ها در یک پارک مخفی شده‌‌اند. این پارک تعدادی نیمکت دارد که این نیمکت‌ها به وسیله‌ی پیاده‌رو‌هایی به هم متصل هستند (به مسیر بین دو نیمکت، که نیمکت دیگری بین آن نباشد یک پیاده‌رو می‌گوییم). برای حرکت در پارک تنها می‌توان از پیاده‌روها عبور کرد. پویزن‌آیوی به اسکیرکرو کمک کرده‌است و در سطح پارک، درختانی رویانیده‌است تا بین هر دو نیمکت تنها یک مسیر وجود داشته باشد. همچنین حرکت بین دو نیمکت متصل به هم، یک دقیقه طول می‌کشد.

    نایت‌وینگ و رابین می‌خواهند تمامی نیمکت‌ها را جستجو کنند. آن‌ها می‌خواهند این جستجو در سریع‌ترین زمان ممکن صورت بگیرد، به همین خاطر می‌خواهند نیمکت‌ها را بین خودشان طوری تقسیم کنند تا هم تمامی نیمکت‌ها دیده‌شود و هم‌چنین هیچ پیاده‌رویی توسط هر دو نفر پیموده نشود. آن‌ها در ابتدا یک نیمکت را انتخاب می‌کنند و در آن‌جا فرود می‌آیند، پس از پایان جستجو آن‌ها می‌خواهند دوباره به همین نیمکت بازگردند. با توجه به این که خطر حمله‌ی اسکیرکرو وجود دارد،‌ آن‌ها می‌خواهند زمانی که در حال جستجو هستند کمینه باشد.

    وظیفه‌ی شما کمک‌کردن به این دو‌نفر برای کمینه‌کردن جستجو با توجه به شرایط گفته‌شده است. نیمکت‌ ابتدایی و تقسیم‌بندی نیمکت‌ها را طوری تعیین کنید تا زمان جستجو کمینه شود.

 

Input

 در خط اول t < 20 می‌آید که تعداد مورد‌هایی است که برنامه‌ی شما باید پاسخ دهد، درخط اول هر مورد‌  n (کوچک‌تر از ۱۰۰) بیان‌گر تعداد نیمکت‌هاست. در n-1 خط بعدی، دو عدد i و j می‌آید که به این معنی است که نیمکت i و j به وسیله‌ی پیاده‌رویی به هم متصل هستند.

Output

برای هر مورد، به ترتیب دو عدد f و s بنویسید که f، شماره‌ی نیمکت ابتدایی و s زمان مورد نیاز برای جستجوی تمام نیمکت‌ها با شروع از نیمکت f و بازگشت هر دو نفر به این نیمکت است. در صورتی که برای نیمکت ابتدایی، چند حالت وجود داشت، کوچکترین شماره‌ را خروجی دهید.

Sample Input

2
5
1 2
2 3
2 4
5 2
10
1 8
8 4
4 3
4 5
5 7
7 2
7 9
7 6
7 10

Sample Output

2 4
5 10

Submit