시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 36 | 23 | 19 | 65.517% |
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.
The first line of the input contains the number of tests $T$ ($1 \leq T \leq 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 \leq k \leq n \leq 100$). The second line contains the description of the tree in a rooted manner: $n - 1$ integers where the $i$-th integer, $p_i$, is the parent of the city $i + 1$ ($1 \leq p_i \leq i$). The capital is the city with the number $1$ --- the root of the tree.
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.
3 6 2 1 1 2 2 3 6 6 1 1 2 2 3 6 4 1 2 3 4 5
1 1 2 8 1 3 6 3 1 2 5 2 4 3 1 2 3 4
The following pictures illustrate all the three tests from the example.