SP1870 MKLABELS - Making Labels

树的种类繁多，不仅限于我们常见的二叉树。通常来说，树就是一种连通无环图，即由若干个顶点 $N$（在本题中假设至少有一个顶点）和 $N-1$ 条边构成，每条边连接两个顶点。 “标记树”是指对树中的每个顶点都进行了标记。为了简化问题，我们假设这些标记是从 1 到 $N$ 的整数。那么，对于一个包含 $N$ 个顶点的树，有多少种不同的标记方式呢？这里的“不同”是指，尽管两个树都有相同数量的顶点，但是由于标记方式的不同，它们无法通过排列变成相同的树。（注意，通常我们会在每个顶点上关联一些数据，或选定一个顶点作为树的根，但这些在本题中无关紧要。） 我们来看一些例子。下图展示了顶点数量为 $N=1, 2, 3, 4, 5$ 的树的所有可能排列。每棵树下方的数字表示该树中顶点能够被标记的不同方式数。  很显然，只有一个顶点的树，只有一种标记方式，即给这个顶点标注为“1”。两个顶点的树也是一样，只有一种标记方式。虽然下图左边的两棵树看似不同，但实际上可以通过简单的变换将第一个变成第二个。（你可以想象这些边是绳子，顶点可以在不失去连接性的情况下轻松移动。）  然而，对于三个顶点的树，有三种不同的标记方法，如图右所示。无论你如何重新排列这三棵标记过的树，都不能变成其他标记方式的树。 同样地，对于四个顶点的树，其各种排列方式共有 16 种标记可能性——其中 12 种是四个顶点形成一条直线的情况，另外 4 种是其他的排列。当 $N=5$ 时，树有三种顶点排列，总计有 125 种标记可能性。

输入包含多个测试用例。每个测试用例是一个整数 $N$，表示树中的顶点数，$N$ 总是介于 1 和 10 之间。输入最后用一个 0 结束。

对于每个测试用例，输出测试用例的编号（如 1, 2, …）、输入的 $N$ 值，以及该树可以被标记的不同方式的数量。输出格式请参照下列示例。

$$1 \le N \le 10$$ **本翻译由 AI 自动生成**