Vài năm trước, Bộ Cơ sở Hạ tầng Bergen đã chuẩn bị một kế hoạch xây dựng mạng lưới đường sắt nhẹ mới. Mạng lưới này sẽ nối tất cả \(n\) khu dân cư của thành phố bằng \(n-1\) đoạn đường ray, sao cho có đường đi từ bất kỳ khu dân cư nào đến bất kỳ khu dân cư nào khác. Các đoạn đường ray trong kế hoạch được đánh số từ \(1\) đến \(n-1\).

Nhiều năm đã trôi qua, cuộc bầu cử mới đang đến gần, nhưng mạng lưới đường sắt vẫn chỉ tồn tại trên giấy. Vì vậy, Bộ trưởng Bộ Cơ sở Hạ tầng, đại diện cho một đảng rất coi trọng sự bất đồng, quyết định xây dựng ít nhất một phần của kế hoạch. Ông yêu cầu mỗi người trong số \(m\) thứ trưởng chọn những khu dân cư mà họ cho rằng cần được nối với nhau. Từ đó, mỗi thứ trưởng sẽ có một danh sách các đoạn đường ray cần thiết. Nếu một thứ trưởng cho rằng các khu dân cư \(a_1,\ldots,a_s\) cần được nối với nhau, thì theo người đó, các đoạn đường ray cần thiết là tất cả những đoạn nằm trên đường đi trong kế hoạch từ \(a_i\) đến \(a_j\) với ít nhất một cặp chỉ số \(1 \le i < j \le s\).

Bộ trưởng vừa nhận được tất cả các danh sách từ các thứ trưởng. Ông quyết định xây dựng trước những đoạn đường ray được ít nhất \(k\) thứ trưởng yêu cầu. Nhiệm vụ của bạn là lập danh sách những đoạn đường ray này.

Ảnh: Bergen Railway Station, Kamil Porembiński, qua Wikimedia Commons; CC-BY-SA-2.0.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(k\).

\(n-1\) dòng tiếp theo mô tả kế hoạch. Dòng thứ \(i\) trong số này chứa hai số nguyên \(a_i\) và \(b_i\) (\(1 \le a_i,b_i \le n\), \(a_i \ne b_i\)), cho biết đoạn đường ray thứ \(i\) nối khu dân cư \(a_i\) với khu dân cư \(b_i\).

\(m\) dòng tiếp theo mô tả những khu dân cư được các thứ trưởng lựa chọn. Dòng thứ \(i\) trong số này bắt đầu bằng số nguyên \(s_i\), là số khu dân cư mà thứ trưởng thứ \(i\) chọn, theo sau là \(s_i\) số nguyên chỉ các khu dân cư đó. Tổng độ dài các danh sách không vượt quá \(S\), tức là \(\sum_{i=1}^{m} s_i \le S\).

Dữ liệu ra

Dòng đầu tiên ghi một số nguyên \(r\): số đoạn đường ray được ít nhất \(k\) thứ trưởng yêu cầu.

Dòng thứ hai ghi \(r\) số hiệu của các đoạn đường ray đó theo thứ tự tăng dần.

Ràng buộc

• \(2 \le s_i \le n \le 100\,000\) với mọi \(1 \le i \le m\).
• \(\sum_{i=1}^{m} s_i \le S \le 100\,000\).
• \(1 \le k \le m \le 50\,000\).
• \(1 \le a_i,b_i \le n\) và \(a_i \ne b_i\) với mọi \(1 \le i \le n-1\).
• Mạng lưới trong kế hoạch có \(n-1\) đoạn đường ray và có đường đi giữa mọi cặp khu dân cư.

Phân nhóm

Bạn chỉ nhận được điểm của một nhóm khi vượt qua tất cả các test trong nhóm đó. Tổng điểm là tổng điểm của các nhóm.

• Nhóm 1 (8 điểm): \(n \le 10\,000\) và \(S \le 2\,000\).
• Nhóm 2 (15 điểm): \(n \le 10\,000\) và \(m \le 2\,000\).
• Nhóm 3 (7 điểm): Mỗi khu dân cư là đầu mút của nhiều nhất \(2\) đoạn đường ray trong kế hoạch.
• Nhóm 4 (29 điểm): \(k=m\) và \(s_i=2\) với mọi \(1 \le i \le m\).
• Nhóm 5 (16 điểm): \(k=m\).
• Nhóm 6 (25 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

2
2 3

Nguồn

Baltic Olympiad in Informatics 2017, ngày thi thứ 1.