Bà H là một doanh nhân và cũng là một nhà hảo tâm lớn. Sắp tới đây bà dự định sẽ có một chuyến đi về miền Trung để hỗ trợ đồng bào bị lũ lụt.

Ban quản lý của bà H đã liệt kê ra được danh sách gồm ~N - 1~ địa điểm có thể đi đến được. Vị trí của bà H và ~N - 1~ điểm trên được nối với nhau bằng các con đường do ban quản lý sắp xếp sẵn, tạo thành một đồ thị gồm ~N~ đỉnh liên thông, vô hướng, và không có chu trình.

Tuy nhiên do tình hình dịch bệnh, Chính phủ quy định chỉ được phép di chuyển tới không quá ~K~ địa điểm khác nhau, vì vậy bà H quyết định sẽ đến chính xác ~K~ địa điểm (bao gồm địa điểm của bà H) để làm từ thiện.

Ban quản lý sẽ đưa cho bạn nhiều bộ dữ liệu khác nhau. Với mỗi bộ dữ liệu bạn hãy giúp bà H chọn ra lộ trình ngắn nhất, xuất phát từ địa điểm ~1~ (vị trí của bà H) và đi qua chính xác ~K~ địa điểm khác nhau (lộ trình có thể đi qua một địa điểm nhiều lần và kết thúc ở địa điểm bất kì). Có thể có nhiều lộ trình ngắn nhất, bạn chỉ cần đưa ra một trong số đó.

Dữ liệu

Dòng đầu tiên gồm một số nguyên ~T~ ~(1 \le T \le 100)~ là số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Dòng thứ ~1~ gồm hai số nguyên ~N~ và ~K~ ~(1 \le K \le N \le 1000)~.

• Dòng thứ ~2~ gồm ~N - 1~ số nguyên ~p_1, p_2, \ldots, p_{N-1}~ ~(1 \le p_i \le i)~, trong đó ~p_i~ mô tả cạnh nối giữa ~p_i~ và ~i + 1~.

Kết quả

Với mỗi bộ dữ liệu:

• Dòng thứ ~1~ gồm một số nguyên ~L~ là độ dài của lộ trình (số cạnh đi qua).

• Dòng thứ ~2~ gồm ~L + 1~ số nguyên ~x_i~, là các điểm nằm trên lộ trình theo thứ tự đi qua.

Ví dụ

Sample Input

3
6 2
1 1 2 2 3
6 6
1 1 2 2 3
6 4
1 2 3 4 5

Sample Output

1
1 2
8
1 3 6 3 1 2 5 2 4
3
1 2 3 4

Giải thích

Hình minh họa cho cả ba bộ dữ liệu trong ví dụ: