← 返回题目列表

Codeforces · 1510/G

G. 指南

中文机器翻译题面 查看原题

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

Guide - 原题 PDF 第 1 页
原题PDF第10页
可复制的 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