Spider tree P98714


Statement
 

pdf   zip

thehtml

A spider mom plans to buy a tree (an undirected and connected graph with no cycles) for its progeny. The spider mom has n kids, and wants a tree with 8n vertices that can be divided into n subtrees with exactly eight vertices each (one subtree for each kid, with one vertex for each of its eight legs), only by removing n − 1 edges. Let us call such a tree a spider tree.

Given a tree with 8n vertices, is it a spider tree?

Input

Input consists of several cases, each with n followed by 8n − 1 pairs x y indicating an edge between x and y. Assume 1 ≤ n ≤ 104, that the given graph is indeed a tree, and that vertices are numbered starting from zero.

Output

For every tree, tell if it is a spider tree or not.

Public test cases
  • Input

    1
    6 1  4 0  1 5  7 1  0 6  3 0  6 2
    
    2
    3 8  11 1  3 15  14 11  11 13  0 4  9 0  6 11  0 3  7 11  2 14  0 14  10 4  14 12  14 5
    

    Output

    yes
    no
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++