UVA10253 Series-Parallel Networks

你需要处理一个计数双端串并联电路图的问题。这是电路在拓扑学和图论中的表示方法。 一个双端图是一个串并联电路图当且仅当它可以被以下的条件表示出来： - 单独的一条边是一个双端串并联电路图； - 将双端串并联电路图的端点分别连接起来，我们可以得到这两个电路的并联电路； - 从两条电路各取一个端点连接起来，我们可以得到这两个电路的串联电路。 如 PDF 题面所示，电路与各个部分的顺序无关。即从左往右依次串联 $A,B,C$ 或者从左往右依次串联 $C,A,B$ 都是等价的。 给你一个数字 $N(1\leq N \leq30)$，请计算 $N$ 条线的电路有多少种不同的形态。 答案有可能不在 $32$ 位整数范围内。

输入包含多组数据，每组数据一行，包含一个数字 $N$。结束标志为 $N=0$。

对于每组数据，输出一行，包含一个整数，即给定线数的电路有多少种。 Translation provided by @Zaoaa