Tree II

Source : Unknown
Time limit : 5 sec Memory limit : 32 M

Submitted : 206, Accepted : 135

    树是计算机中非常重要的非线性结构。对树本身的形态进行思考与研究,是一个 十分有趣且具有挑战性的过程。 我们对一个树的正式定义是:

    1.一个结点 x 组成的集 {x} 是一株树。 这个结点 x 也是这株树的根。
    2.假设 x 是一个结点, T1 ,T2 ,...,TK 是 K 株互不相交的树,我们可以构造一株新树:令 x  为根,并有 K 条边由 x 指向树 T1 ,T2 ,...,TK。这些边也叫做 分支,T1 ,T2 ,...,TK称作根为  x 的树的子树(subtree)。
                                                   ——《数据结构》 大连理工大学出版社


    连通的无圈图称为自由树。如果选定自由树中的某个顶点 作树根,以树根为起点对每条边定向,就能把一棵自由树变成一棵通常的树。
                                                   ——《数据结构与算法》


    自由树与通常所说的树很相似,它包括有结点和分支, 但不含有根。自由树结点间只有相邻关系,而不存在父子结点关系。 容易发现,对某棵自由树,指定其一个结点为根结点后, 我们将得到一棵有根树。 对于两棵自由树甲和乙,任取自由树甲的某个结点作为 根结点,形成一棵有根树丙。若存在以自由树乙的某结点为根的有根树丁与丙同构, 则称甲乙两树同构


输入

    输入包含一个非负整数序列。对于每个输入的N (1<=N<=200),求出 结点个数为N的自由树总数。输入以0结束。

输出

    每个结果一行

输入样例
1
2
3
0
输出样例
1
1
1