Spider tree P98714

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 ≤ 10⁴, 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.