1004. 今晚吃转转

题目描述

即便是最细小的枝桠也能孕育无限可能。

地脉正在颤动，世界树岌岌可危。 原本的世界树可以被看作一棵包含 $n$ 个点与 $n-1$ 条边的无根树 $Y$ 被绘制在平面上。$Y$ 中的第 $i$（$1\le i\le n$）个点在坐标 $\lparen x_i,y_i\rparen$（$x_i,y_i\in\mathbb{R}$）处，点的坐标两两不同。$Y$ 的每条边都是连接两个端点的线段，连接后平面上的图形就被称为 $Y$ 的图像。注意，图像不能进行平移，缩放，旋转，轴对称等任何操作。

由于地脉紊乱，世界树被迫旋转。 现在，平面中出现了一个紊乱点 $\lparen p,q\rparen$（$p,q\in\mathbb{R}$），使得世界树 $Y$ 的图像以 $\lparen p,q\rparen$ 为中心顺时针旋转了 $\frac{2\pi}{k}$ 弧度，其中 $k$ 是一个正整数。注意紊乱点坐标是任意的，可以与世界树某一个点重合，也可以落在世界树某一条边上。

作为新生的小吉祥草王，纳西妲只知道世界树 $Y$ 的形态而不知道它的图像。纳西妲想要知道，对于哪些正整数 $k$，存在一个为 $Y$ 中每个点赋予两两不同的坐标以及选取紊乱点坐标的方式，使得：

• $Y$ 的图像中，任意两条边对应的线段除公共端点外不相交（包括某一条边的端点落在另一条边上的情况）。
• $Y$ 的图像旋转后与其旋转前完全重合。

注意，判断重合时不能进行平移，缩放，旋转，轴对称等任何操作。

输入格式

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 10^3$）表示测试数据组数。

接下来对于每一组测试数据：

第一行包含一个整数 $n$（$2\le n\le 2\times 10^5$，$\sum n\le 10^6$），表示世界树的大小。

接下来 $n-1$ 行，第 $i+1$（$1\le i<n$）行包含两个整数 $u_i,v_i$（$1\le u_i,v_i\le n$），表示第 $i$ 条边连接的两个端点。

输出格式

对于每一组测试数据：

第一行包含一个整数 $c$，表示满足条件的正整数 $k$ 的个数。

第二行包含 $c$ 个整数 $k_1,k_2,k_3,\cdots,k_c$（$1\le k_1<k_2<k_3<\cdots<k_c$），表示每个满足条件的正整数 $k$。

样例输入

2
10
1 2
2 3
3 4
4 5
2 7
4 6
3 8
8 9
8 10
8
1 2
1 3
1 4
1 5
1 6
1 7
2 8

样例输出

2
1 3
4
1 2 3 6

提示

以第一组测试数据为例，一个 $k=3$ 的合法点坐标为（按照编号顺序）：

$\lparen 6,4\rparen,\ (5,4),\ (3,4),\ (2,4+\sqrt{3}),\ \left(\frac{3}{2},4+\frac{3\sqrt{3}}{2}\right),$

$\left(3-\frac{5\sqrt{3}}{4},\frac{21}{4}\right),\ \left(3+\frac{5\sqrt{3}}{4},\frac{21}{4}\right),\ (2,4-\sqrt{3}),\ \left(\frac{3}{2},4-\frac{3\sqrt{3}}{2}\right),\ \left(3,\frac{3}{2}\right)$

紊乱点为 $\lparen 3,4\rparen$。此时旋转后图像与原本图像完全重合，图像如图所示：


来源：2026杭电多校-测试专用（南外） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1235&pid=1004