CF2253E Diameter Intersections

You are given a tree with $ n $ vertices. The diameter of a tree is a simple path of maximum length in the tree. The length of a path is the number of edges it contains. The diameter of the given tree has odd length. We call an integer $ k $ beautiful if it is possible to choose two diameters in this tree (possibly with the same endpoints; it is allowed to choose the same two diameters) such that their intersection contains exactly $ k $ edges. Find all beautiful values of $ k $ and output them in increasing order.

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case is given in the following format: - the first line contains one integer $ n $ ( $ 2 \le n \le 10^6 $ ) — the number of vertices in the tree; - the next $ n - 1 $ lines contain two integers $ u $ and $ v $ each ( $ 1 \le u, v \le n $ , $ u \ne v $ ), denoting an edge between vertices $ u $ and $ v $ . Additional constraints on the input: - the sum of $ n $ over all test cases does not exceed $ 10^6 $ ; - in each test case, the edges form a tree whose diameter has odd length.

For each test case, print one integer $ m $ — the number of beauitful values of $ k $ ; then print the values of $ k $ themselves in increasing order.

Consider the first three examples: - in the first example, the pair of diameters $ (1, 2) $ and $ (1, 2) $ gives $ k=1 $ ; - in the second example, the pair of diameters $ (1, 4) $ and $ (4, 1) $ gives $ k=3 $ ; - in the third example, the pair of diameters $ (6, 4) $ and $ (3, 5) $ gives $ k=1 $ ; the pair of diameters $ (6, 4) $ and $ (4, 5) $ gives $ k=2 $ ; the pair of diameters $ (6, 4) $ and $ (6, 4) $ gives $ k=3 $ .