Liên thông quận

Thành phố Hồ Chí Minh (thường được gọi là Sài Gòn) là một thành phố ở miền nam Việt Nam nổi tiếng với vai trò nòng cốt trong chiến tranh Việt Nam. Sài Gòn cũng được biết đến với địa danh của thực dân Pháp, trong đó có Nhà thờ Đức Bà được xây dựng hoàn toàn bằng nguyên liệu nhập khẩu từ Pháp và Bưu điện trung tâm được xây dựng vào thế kỷ 19. Quán ăn nằm dọc các đường phố Sài Gòn, nhất là xung quanh chợ Bến Thành nhộn nhịp.

Đến thành phố Hồ Chí Minh, các bạn có thể tham quan những địa điểm sau:

• Trụ sở Ủy ban Nhân dân Thành phố

• Bến Nhà Rồng: nơi Chủ tịch Hồ Chí Minh ra đi tìm đường cứu nước, Bến Nhà Rồng còn có tên gọi khác là bảo tàng Hồ Chí Minh tại thành phố Hồ Chí Minh, ở trong có các kỉ vật của Bác Hồ.

• Nhà hát lớn
• Bưu điện Trung tâm

• Dinh Độc lập: Công trình được thiết kế theo phong thuỷ và kiến trúc phương Đông nhưng lại rất hiện đại. Tham quan dinh Độc Lập, du khách có thể chiêm ngưỡng tận mắt nhiều vật phẩm từ chế độ cũ cũng như những chứng tích ghi dấu thời khắc ngày độc lập 30 tháng 4, 1975. Giờ mở cửa: Sáng 7h30 -- 11h00, chiều từ 13h00 -- 16h00 (hàng ngày); Địa chỉ: 135 Nam Kỳ Khởi Nghĩa, P.Bến Nghé, Q.1; Giá vé: Người lớn:30.000VND/người/lần, sinh viên: 15.000VND/người/lần, học sinh: 3.000VND/người/lần, khách theo đoàn từ 20 người sẽ được giảm 1/3 giá vé; Gửi xe máy tại: Cổng Dinh Độc Lập bên đường Nguyễn Du, bãi gửi xe ở công viên Tao Đàn trên đường Huyền Trân Công Chúa.

• Nhà thờ Đức Bà: Đây là khu vực trung tâm thuộc Q.1, Thành phố Hồ Chí Minh. Khu vực Nhà Thờ thể hiện rõ rệt "tính cách" của thành phố Sài Gòn. Gần nhà thờ cổ kính là hình ảnh đối lập với những tòa cao ốc bê tông cốt thép thời hiện đại. Từ nhà thờ Đức Bà, bạn có thể sang thăm dinh Độc Lập, mua sắm ở Diamond Plaza, dạo phố Đồng Khởi, qua Hồ Con Rùa, uống cà phê bệt ở đường Hàn Thuyên. Tọa lạc ngay trục đường chính ở trung tâm thành phố, hiện nay nhà thờ Đức Bà dần trở thành biểu tượng của thành phố Sài Gòn. Nơi đây nổi bật với kiến trúc Châu Âu kết hợp phong cách Roman và Gothic tuyệt đẹp, cùng cặp chuông lớn nhất Việt Nam. Nhà thờ Đức Bà là ngôi thánh đường đẹp nhất và quan trọng nhất của giáo phận Sài Gòn, niềm tự hào của người dân thành phố. Khu vực xung quanh nhà thờ Đức Bà có cảnh quan đẹp nhất tại Sài Gòn.

• Thảo Cầm viên
• Công viên 23/9
• Bảo tàng Chứng tích chiến tranh: Du khách đến đây sẽ cảm nhận chân thực nhất về một thời kỳ chiến tranh ác liệt, để thêm trân trọng những gì đang có ở hiện tại. Các hiện vật như máy bay, đại bác, xe tăng, máy chém và hai ngăn "chuồng cọp" được xây dựng đúng kích thước ở nhà tù Côn Đảo. Ngoài ra còn có phòng trưng bày về Chiến tranh biên giới Tây Nam, chiến tranh bảo vệ biên giới phía Bắc, vấn đề quần đảo Trường Sa, âm mưu của các thế lực thù địch… Giờ mở cửa: Sáng 7h30 -- 12h00, 13h30 -- 17h00 (hàng ngày); Vé vào cổng: 15.000VND/lượt/người (khách nước ngoài), 2.000VND/lượt (khách Việt Nam); Địa chỉ: Số 28 đường Võ Văn Tần, Q.3.
• Bảo tàng Chiến dịch Hồ Chí Minh

Quân hiện tại đang sinh sống và học tập tại thành phố Hồ Chí Minh. Hiện tại, thành phố Hồ Chí Minh có 16 quận : Quận 1, quận 3, quận 4, quận 5, quận 6, quận 7, quận 8, quận 10, quận 11, quận 12, quận Tân Bình, quận Tân Phú, quận Bình Tân, quận Bình Thạnh, quận Gò Vấp và quận Phú Nhuận. Tuy nhiên, trong một tương lai nào đó, thành phố Hồ Chí Minh lúc này có \(n\) quận, được kết nối với nhau bằng \(n - 1\) con đường nối trực tiếp giữa hai quận khác nhau, đảm bảo giữa \(n\) quận đều có thể đi đến được với nhau bằng những con đường này. Tuy nhiên, vì một trận mưa lớn, tất cả các con đường đều bị ngập và các quận đều bị cô lập.

Tình hình này không thể diễn ra liên tục, vì nó ảnh hưởng rất lớn tới thành phố. Chính phủ quyết định sẽ dùng máy hút nước siêu khổng lồ để hút nước tại các con đường. Máy hút nước này được sử dụng như sau:

• Có \(m\) kế hoạch hút nước. Kế hoạch hút nước thứ \(i\) sẽ hút nước trên một số con đường, sao cho sau khi hút nước xong, các quận \(a_{1}, a_{2}, ..., a_{s}\) sẽ đi đến được với nhau, và số con đường hút nước phải ít nhất. Lưu ý: dù các con đường ở các kế hoạch trước đã hút nước, ở kế hoạch hiện tại vẫn phải hút.

Yêu cầu: Đếm số con đường bị ảnh hưởng bởi ít nhất \(k\) kế hoạch.

Input

Dòng đầu tiên là ba số nguyên dương \(n, m, k\).

\(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(a_{i}\) và \(b_{i}\) - con đường kết nối hai quận \(a_{i}\) và \(b_{i}\) \((1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i}\).

\(m\) dòng tiếp theo, mỗi dòng gồm :

• số nguyên dương \(s\) là số quận đi đến được với nhau sau khi hút nước.

• tiếp theo là \(s\) số nguyên dương \(a_{1}, a_{2}, ..., a_{s}\) $(1 \leq a_{i} \leq n, a_{i} \neq a_{j} (i \neq j)) $.

Dữ liệu đảm bảo rằng tổng của các \(s\) trong các kế hoạch không vượt quá \(S\).

Output

Dòng đầu tiên là số nguyên không âm \(r\), số con đường bị ảnh hưởng bởi ít nhất \(k\) kế hoạch.

Dòng thứ hai là chỉ số của các con đường bị ảnh hưởng, theo thứ tự tăng dần.

Example

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 

Scoring

Trong tất cả các testcase, \(2 \leq s_{i} \leq n, S \leq 100000, 1 \leq k \leq m \leq 50000\).

Có \(8\%\) số test tương ứng với \(8\%\) số điểm có \(n \leq 10000, S \leq 2000\).

Có \(15\%\) số test tương ứng với \(15\%\) số điểm có \(n \leq 10000, m \leq 2000\).

Có \(7\%\) số test tương ứng với \(7\%\) số điểm có mỗi quận chỉ kết nối tối đa \(2\) quận khác.

Có \(29\%\) số test tương ứng với \(29\%\) số điểm có \(k = m, s_{i} = 2\).

Có \(16\%\) số test tương ứng với \(16\%\) số điểm có \(k = m\).

Có \(25\%\) số test tương với với \(25\%\) số điểm còn lại không có ràng buộc gì thêm.