All Tracks Algorithms Graphs Depth First Search Problem

AltF4 and Spinal Network
Tag(s):

Medium

Problem
Editorial
Analytics

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.

Constraints
T ≤ 500
N ≤ 10000
1 ≤ U, V ≤ N

SAMPLE INPUT
2
4
4 1
4 2
4 3
7
7 1
7 2
7 3
1 4
2 5
3 6
SAMPLE OUTPUT
YES
NO
Explanation

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Rain

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?