AltF4 is into his networking class and his teacher introduces him to bus topology. Being bored of the class, he his lost into his own thoughts where he discovers a new topology of his own - the Spinal Network. In this topology, we have a central line just like the bus topology. All the nodes (or hops, or computers) are either in the central line itself, or it is directly connected to the central line. To make things easier he says that the topology given should be a tree. Resembles the spinal cord, isn't it? Given a tree, you need to figure out if it is spinal or not.
Input & Output
The first line of the input contains the number of test cases T. Description of T test cases follow. Each test case starts with an integer N the number of nodes in the tree. N - 1 lines follow each containing two integers U V, the nodes which have an edge between them.
NOTE : Large Input Files. Use faster IO.For each test case, output "YES" if the tree given is Spinal else output "NO". Quotes are for clarity only and should not be printed.
ConstraintsT ≤ 500 N ≤ 10000 1 ≤ U, V ≤ N
1) In the first test case, the tree can be drawn as : 1--4--2 | 3 If we consider, 1-4-2 to be the central line - all nodes are either on it or directly connected to it.
2) In second case, tree can be drawn as: 4-1-7-2-5 | 3 | 6 As we can see, node with label 6 does not satisfy the conditions given.
