#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 1e5 + 5;
const int LOG = 17;
int n, m, threshold; // n: số nút, m: số truy vấn (phó bộ trưởng), threshold: số k (ít nhất k phó bộ trưởng)
vector<pair<int, int>> edges; // danh sách cạnh: mỗi cạnh nối hai nút (u, v)
vector<int> adj[NMAX]; // danh sách kề lưu trữ chỉ số của cạnh
int st[NMAX], en[NMAX]; // thời gian vào và ra của mỗi nút trong DFS
int timer = 0;
int parentEdge[NMAX]; // parentEdge[v] lưu chỉ số cạnh nối v với cha của nó
int anc[NMAX][LOG]; // bảng tổ tiên dùng cho truy vấn LCA
int add[NMAX]; // mảng hiệu dùng để lưu số lần "yêu cầu" của các cạnh
vector<int> result; // danh sách kết quả (các cạnh được yêu cầu đủ số phi bộ trưởng)
// DFS tiền xử lý: tính thời gian vào/ra và xây dựng bảng tổ tiên
void dfsPreprocess(int u, int p) {
st[u] = ++timer;
anc[u][0] = p; // tổ tiên cấp 0 là cha của u
for (int i = 1; i < LOG; i++) {
anc[u][i] = anc[anc[u][i-1]][i-1];
}
// duyệt các cạnh từ u
for (int edgeIdx : adj[u]) {
// Tìm nút đối diện của u trên cạnh edgeIdx
int v = (edges[edgeIdx].first == u ? edges[edgeIdx].second : edges[edgeIdx].first);
if (v == p) continue;
parentEdge[v] = edgeIdx; // lưu lại cạnh nối v với u
dfsPreprocess(v, u);
}
en[u] = timer;
}
// Kiểm tra: u có là tổ tiên của v không?
bool isAncestor(int u, int v) {
return st[u] <= st[v] && en[v] <= en[u];
}
// Tìm LCA của hai nút u và v
int lca(int u, int v) {
if (isAncestor(u, v)) return u;
for (int i = LOG - 1; i >= 0; i--) {
if (!isAncestor(anc[u][i], v))
u = anc[u][i];
}
return anc[u][0];
}
// DFS duyệt lại cây để cộng dồn các giá trị hiệu và xác định các cạnh đạt yêu cầu
int dfsAggregate(int u, int p) {
int sum = 0;
for (int edgeIdx : adj[u]) {
int v = (edges[edgeIdx].first == u ? edges[edgeIdx].second : edges[edgeIdx].first);
if (v == p) continue;
int curVal = dfsAggregate(v, u) + add[edgeIdx];
// Nếu số lần yêu cầu của cạnh >= threshold, thêm vào kết quả
if (curVal >= threshold) {
result.push_back(edgeIdx);
}
sum += curVal;
}
return sum;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Đọc dữ liệu: n - số nút, m - số truy vấn, threshold - yêu cầu tối thiểu
cin >> n >> m >> threshold;
// Đọc cây (n-1 cạnh). Mỗi cạnh được đánh số từ 0 đến n-2.
for (int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
int edgeIdx = edges.size();
edges.push_back({u, v});
// Thêm cạnh vào danh sách kề của cả hai nút
adj[u].push_back(edgeIdx);
adj[v].push_back(edgeIdx);
}
// Tiền xử lý DFS để tính st, en và bảng LCA
parentEdge[1] = -1; // nút gốc không có cạnh nối từ cha
dfsPreprocess(1, 0);
// Xử lý từng truy vấn của phó bộ trưởng
// Mỗi truy vấn: đầu tiên là số s (số nút trong danh sách), sau đó là danh sách các nút.
for (int i = 0; i < m; i++){
int s;
cin >> s;
vector<int> nodes(s);
for (int j = 0; j < s; j++){
cin >> nodes[j];
}
// Sắp xếp các nút theo thời gian vào của DFS
sort(nodes.begin(), nodes.end(), [](int a, int b){
return st[a] < st[b];
});
// Xử lý các cặp liên tiếp theo thứ tự sắp xếp
// Ý tưởng: nối dần các nút theo thứ tự, cập nhật hiệu dương ở đầu đoạn và hiệu âm tại điểm chung (LCA)
int currentLCA = nodes[0];
for (int j = 1; j < s; j++){
int nextNode = nodes[j];
// Tìm LCA của currentLCA và nextNode
int common = lca(currentLCA, nextNode);
// Cập nhật: tăng đếm từ nextNode lên (qua cạnh nối đến cha)
add[parentEdge[nextNode]] += 1;
// Giảm đếm tại cạnh của nút common (điều chỉnh trùng lặp)
if (parentEdge[common] != -1) {
add[parentEdge[common]] -= 1;
}
currentLCA = nextNode; // nối dần
}
}
// Duyệt lại cây để tổng hợp giá trị trên các cạnh
dfsAggregate(1, 0);
// Sắp xếp kết quả theo thứ tự tăng dần (lưu ý: chuyển chỉ số cạnh về 1-index khi in)
sort(result.begin(), result.end());
cout << result.size() << "\n";
for (int edgeIdx : result)
cout << edgeIdx + 1 << " ";
return 0;
}
