Условие
J. GAME
---
Иван и Петър обичат нестандартни игри. Неотдавна те попаднали в изоставена мина състояща се от N зали, номерирани от 1 до N, и N – 1 галерии. Всяка галерия свързва някои две от залите, никои две зали не са свързани с повече от една галерия и от всяка зала може да се стигне до всяка друга зала по единствен начин. Играта се състои в следното. Иван се скрива в зала с номер X, а Петър трябва да открие къде се намира Иван, като избере едно множество S от зали, а Иван му съобщи каква е дължината на пътя от X до всяка от залите в S, изразена в брой галерии, които образуват съответния път. Разбира се, че Петър трябва да избере S така, че да е с колкото може по-малко елементи. Напишете програма, която по зададен план на мината да определи броят на елементите в едно минимално множество, с което Петър да може да открие Иван.
Вход: На първия ред на стандартния вход ще бъде зададен броят T на тестовите случаи. Всеки тест започва с ред с броя N на залите (5 ≤ N ≤ 100). На всеки от следващите N – 1 реда ще бътат зададени, разделени с един интервал, двата края на една от галериите.
Изход: За всеки тестов случай, програмата трябва да изведе на отделен ред на стандартния изход намерения минимален брой зали, с помощта на които Петър да открие Иван.
Примерен вход:
1
6
1 6
2 5
3 4
4 6
5 6
Примерн изход:
2
« Предходна страница
Решение
Въпрос