以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

可复制的 PDF 提取文本
ICPC 2020–2021, NERC – Northern Eurasia Finals, Onsite
St. Petersburg, Minsk, Tbilisi, Riga – April 4th, 2021
Problem G. Guide
Time limit: 3 seconds
Memory limit: 512 megabytes
Mister Gooti is the world-famous guide of The Freezing Isles. The topology of the Isles can be represented
as a tree with cities at the vertices and two-way roads between them. Gooti prepares a new sightseeing
tour over the Isles. He wants to find the shortest path that starts in the capital and visits k different
cities, including the capital. Please, help him.
Input
The first line of the input contains the number of tests T (1 ≤T ≤100). Each test consists of two lines.
The first line contains the overall number of cities n in the Isles and the requested number of cities k for
the tour (1 ≤k ≤n ≤100). The second line contains the description of the tree in a rooted manner: n−1
integers where the i-th integer, pi, is the parent of the city i + 1 (1 ≤pi ≤i). The capital is the city with
the number 1 — the root of the tree.
Output
For each test, the first line of the output shall contain the length of the path l. The second line shall
contain l + 1 integers — the cities that lie on the path in the order of the traversal.
Example
standard input standard output
3 1
6 2 1 2
1 1 2 2 3 8
6 6 1 3 6 3 1 2 5 2 4
1 1 2 2 3 3
6 4 1 2 3 4
1 2 3 4 5
Note
The following pictures illustrate all the three tests from the example.
1
2
1 1 3
2 3 2 3 4
4 5 6 4 5 6 5
Page 10 of 14