Cactus

Time Limit: 20000/10000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      Vertex cactus is a connected undirected graph in which every vertex lies on at most one simple cycle. A tree can be converted to a vertex cactus by adding zero or more edges to it. There can be several ways to convert a tree to cactus. The number of ways to do so determines the cactusability of a tree.
      For example, the cactusability of the tree on the left picture is 12. The twelve cactuses that it can be converted to are shown on the right.

      Given a tree, you have to find its cactusability.

Input

      The first line of the input file contains one integer number n — the number of vertices in a tree (1 ≤ n ≤ 200). The next n − 1 lines contain edges of a tree.

Output

      Write to the output file a single integer number — the cactusability of the given tree.

Sample Input

6
1 3
2 3
3 4
4 5
4 6

Sample Output

12

Hint

戳我下载全套pdf

java is not allowed

Source

Andrew Stankevich Contest 16

Manager

Information
Solved Number1
Submit Number8
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel