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 8*n* 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 8*n* vertices, is it a spider tree?

**Input**

Input consists of several cases,
each with *n* followed by 8*n* − 1 pairs *x* *y*
indicating an edge between *x* and *y*.
Assume 1 ≤ *n* ≤ 10^{4},
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++