好的，这是整理好的标准题目描述，包含样例解释，适合上传平台。

---

题目描述

求 $N$ 个有标号节点（编号 $1 \sim N$）的无向连通图有多少个。

例如，三个节点的无向连通图共 $4$ 个（见下图示例）。

下图展示了 $N = 3$ 时的所有无向连通图（不考虑同构图，只考虑标号图）：

（图片示意：三个节点的四种连通图）

• 三角形（3 条边）
• 链状：1—2—3
• 链状：1—3—2
• 链状：2—1—3

你需要对每组输入的 $N$ 输出答案。

注意：

• 图中不允许有自环。
• 图中不允许有重边。
• 两个图不同当且仅当边集不同（因为节点标号固定）。

---

输入格式

输入包含多组测试数据。
每组数据一行，一个整数 $N$。
当输入为 0 时，表示输入终止。

输出格式

每组测试数据输出一行，表示 $N$ 个有标号节点的无向连通图的个数。

---

数据范围

$1 \le N \le 50$

---

输入样例

1
2
3
4
0

输出样例

1
1
4
38

---

样例解释

$N = 1$

只有一个节点，没有边，该图是连通的（单个节点总是连通的），所以答案是 1。

$N = 2$

两个节点，只有一种方法让它们连通：用一条边连接。
没有其他方式（因为不能有重边或自环），所以答案是 1。

$N = 3$

所有可能的连通图：

1. 边集：$\{(1,2),(2,3)\}$（链状）
2. 边集：$\{(1,2),(1,3)\}$（星型）
3. 边集：$\{(1,3),(2,3)\}$（链状）
4. 边集：$\{(1,2),(2,3),(1,3)\}$（三角形）

一共 $4$ 种，所以输出 4。

$N = 4$

计算可得有标号连通图数量为 38（需要组合计数或递推求出）。
具体构造较繁琐，但已知结果为 38。

---

计算方法提示：
设 $g(n)$ 为 $n$ 个有标号节点的所有无向图个数（不一定连通），则：

$$g(n) = 2^{C(n,2)} = 2^{\frac{n(n-1)}{2}}$$

设 $f(n)$ 为 $n$ 个有标号节点的连通无向图个数，可以利用容斥原理或 DP 递推：

$$f(n) = g(n) - \sum_{k=1}^{n-1} C(n-1, k-1) f(k) g(n-k)$$

或者用指数生成函数方法。
对于 $N=4$：

• $g(4) = 2^{6} = 64$
• 需要排除不连通的情况，计算可得 $f(4) = 38$。