Module: Hashing


Problem

8 /8


Bunkers

Theory Click to read/hide

There are also several ways to efficiently hash rooted trees. 
One of these methods is arranged as follows:
We process the vertices recursively, in order of traversal in depth. We will assume that the hash of a single vertex is equal to p. For vertices with children, we first run the algorithm for them, then through the children we will calculate the hash of the current subtree. To do this, consider the hashes of subtrees of children as a sequence of numbers and calculate the hash from this sequence. This will be the hash of the current subtree.
If the order on the children is not important to us, then before calculating the hash, we sort the sequence of hashes from the child subtrees and then calculate the hash from the sorted sequence.

This way you can check the isomorphism of trees - just count the hash without order on the children (that is, each time sorting the hashes of the children). And if the hashes of the roots match, then the trees are isomorphic, otherwise not.

For unrooted trees, everything happens in a similar way, but the centroid must be taken as the root. Or consider a pair of hashes if there are two centroids.

Problem

Petya and Vasya enthusiastically play spies. Today they are planning where they will be 
located their secret bunkers and headquarters. 

So far, Petya and Vasya have decided that they will need exactly n bunkers, which will be numbered from 1 to n for secrecy. 
Some of them will be connected by two-way tunnels, and for reliability and secrecy, the tunnels will be accessible from any bunker to any one way.
Petya and Vasya even decided which of the bunkers will be connected by tunnels, but they cannot choose which one will be the headquarters. 
The boys want to choose it and divide the remaining bunkers among themselves so that they get an equal number of bunkers. Exactly two tunnels lead to the headquarters: one from the bunker belonging to Vasya, the other from the bunker belonging to Petya. 
                                                                                   
Tired Petya went to his house, and in the morning Vasya showed him a plan on which the bunkers were marked with dots and the tunnels with segments. 
In addition, Vasya chose the headquarters in such a way that the plan he drew was symmetrical with respect to a straight line passing through the point that corresponded to the headquarters.
 
Although Petya almost immediately showed Vasya that he had made a mistake and did not draw half of the bunkers, he wondered if it was possible to choose a headquarters and draw such a symmetrical plan.

Input:
The first line of the input file contains a single integer n (1 <= n <= 105) - the number of bins. 
The next n - 1 lines contain two integers ui and vi (1 <= ui, vi <= n, ui ≠ vi) - numbers of bunkers connected by the i-th tunnel. 
It is guaranteed that there is only one path between any two bunkers.

Output:
In the output file print "YES" if it is possible to choose a headquarters and draw such a plan, or "NO" if that's not possible.

Examples:
 
Input Output
2
1 2 		NO
3
1 2
2 3 		YES

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!