CF291E Tree-String Problem

A rooted tree is a non-directed connected graph without any cycles with a distinguished vertex, which is called the tree root. Consider the vertices of a rooted tree, that consists of $ n $ vertices, numbered from 1 to $ n $ . In this problem the tree root is the vertex number 1. Let's represent the length of the shortest by the number of edges path in the tree between vertices $ v $ and $ u $ as $ d(v,u) $ . A parent of vertex $ v $ in the rooted tree with the root in vertex $ r $ $ (v≠r) $ is vertex $ p_{v} $ , such that $ d(r,p_{v})+1=d(r,v) $ and $ d(p_{v},v)=1 $ . For example, on the picture the parent of vertex $ v=5 $ is vertex $ p_{5}=2 $ . One day Polycarpus came across a rooted tree, consisting of $ n $ vertices. The tree wasn't exactly ordinary: it had strings written on its edges. Polycarpus positioned the tree on the plane so as to make all edges lead from top to bottom if you go from the vertex parent to the vertex (see the picture). For any edge that lead from vertex $ p_{v} $ to vertex $ v $ $ (1<v

The first line contains integer $ n $ $ (2

Print a single integer — the required number. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

In the first test case string "aba" is determined by the pairs of positions: (2, 0) and (5, 0); (5, 2) and (6, 1); (5, 2) and (3, 1); (4, 0) and (4, 2); (4, 4) and (4, 6); (3, 3) and (3, 5). Note that the string is not defined by the pair of positions (7, 1) and (5, 0), as the way between them doesn't always go down.