481. Hero of Our Time
Time limit per test: 0.5
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
Saratov ACM ICPC teams have a tradition to come together on Halloween and recollect terrifying stories. And the most popular story among the newcomers is the story about the "Mescher Tree". A long time ago, when the famous Dmitry Mescheryakov aka Mescher was very young and he even didn't know how to write Dijkstra algorithm, he faced a difficult problem with a tree. Input file contained
n — the number of vertices, and pairs of vertices, connected with an edge. Without thinking a lot (honestly, the exact reason of that mistake is unknown), he wrote the following code:
read(n);
for i := 1 to n do begin
read(u, v);
g[u, v] := true;
g[v, u] := true;
end;
Mescher successfully compiled his code, got WA on sample test and started long debugging... This story has become a true legend. So it's no surprise that Saratov ACM ICPC teams use the following definition: connected undirected graph with
n vertices and
n edges is called
Mescheryakov Tree or, less formally,
Mescher Tree. The area of application of
Mescher trees is not wellstudied, so we suggest you to solve one of the problems connected with such trees: given
n, find the number of distinct
Mescher trees with
n vertices. Trees are labeled, i.e. two trees are considered distinct if and only if their adjacency matrices differ.
Input
Input contains single integer number
n (3 ≤
n ≤ 5000).
Output
Output the number of
Mescher trees with
n vertices without leading zeroes.
Example(s)
sample input

sample output

3

1
