Alexander is a well-known king. His reign extended beyond the boundaries of Europe, Asia, and Africa. The world was at his feet at the peak of his ever-conquesting life. Below is a not-so-well-known story of his.
There is a beautiful small country of island named Formosa. It was said that when Alexander's vessel passed through the Taiwan Strait, he was totally stunned by the magnificence of the island that he shouted "F... F... F... Formosa!! Formosa!!!" Obviously what he intended to say is the "F-word", but managed to changed his mind (or his tongue) midway to honor his position as a mighty King.
Anyway, seeing such a gorgeous island, Alexander the Great decided to conquer Formosa. At the time, there are only N towns in Formosa. Some towns are connected by bidirectional roads, and each pair of towns has exactly one simple route to go from one to another. To control the island, Alexander planned to conquer all towns that appear on in least one longest path. Before doing so, he wanted to know, how many connected components had he NOT conquered after all the towns he planned to attack are taken? Or in other words, how many connected components are there amongst those towns not attacked?
"The bigger the sword, the smaller the brain", as the saying goes. Alexander has a very big sword, so eventually he comes to you for help. Solve the problem for him, or we might as well be able to see how big your brain is.
The first line contain an integer T --- the number of tests(1<=T<=25).
Each test begins with one line only contains one integer N(0<=N<=100000), denoting the number of towns in Formosa.
Then following N-1 lines, each line contains two integer x,y, representing one road connects x-th town and y-th town
(the towns is numbered by 0 to N-1).
For each test, you have to print one line contains the answer of Alexander's question.
3 4 1 2 2 3 2 0 6 0 1 1 2 2 3 3 4 2 5 7 0 1 1 2 2 3 3 4 2 5 2 6
0 1 2
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|