철도
시간 제한1초메모리 제한512 MB
트리와 여러 정점 집합이 주어질 때, 각 간선이 몇 개의 집합에 포함되는지 세어 k개 이상의 집합이 지나는 간선을 모두 구한다.
문제
몇 해 전 베르겐 기반시설부는 새로운 경전철망 계획을 세웠다. 이 철도망은 도시의 모든 n개 지역을 n−1개의 선로로 연결해서, 모든 지역에서 다른 모든 지역으로 가는 경로가 있도록 만드는 것이었다. 계획된 선로에는 1부터 n−1까지 번호가 붙어 있다.
세월이 흘러 새 선거가 다가오지만 철도망은 여전히 종이 위에만 존재한다. 그래서 기반시설부 장관(이견을 높이 평가하는 정당 소속이다)은 계획의 일부라도 건설하기로 했다. 장관은 m명의 차관에게 어느 지역을 연결해야 한다고 생각하는지 각자 고르라고 했다. 그러면 차관마다 필요한 선로 목록이 나온다. 차관이 지역 a1, . . . , as를 연결해야 한다고 생각하면, 그 차관에게 필요한 선로는 어떤 1 ≤ i < j ≤ s에 대해 ai에서 aj로 가는 계획상의 경로 위에 있는 모든 선로이다.
장관은 방금 모든 차관의 목록을 받았다. 장관은 먼저 k명 이상의 차관이 요청한 선로를 건설하기로 했다. 이 선로들의 목록을 구하는 것이 여러분의 과제이다.
입력
입력의 첫 줄에 세 정수 n, m, k가 주어진다. 다음 n−1개 줄에 계획이 주어진다. 이 중 i번째 줄에는 두 정수 ai와 bi(1 ≤ ai, bi ≤ n, ai ≠ bi)가 주어지며, 계획의 i번째 선로가 지역 ai와 bi 사이에 있음을 나타낸다.
다음 m개 줄에는 차관이 고른 지역이 주어진다. i번째 줄은 i번째 차관이 고른 지역의 수를 나타내는 정수 si로 시작한다. 그 뒤에 이 지역들을 나타내는 si개의 정수가 주어진다. 모든 차관 목록의 총 길이는 S 이하, 즉 ∑si ≤ S이다.
출력
출력의 첫 줄에 k명 이상의 차관이 요청한 선로의 수를 나타내는 정수 r을 출력한다. 둘째 줄에 이 선로들의 번호 r개를 오름차순으로 출력한다.
제한
항상 2 ≤ si ≤ n ≤ 100 000, S ≤ 100 000, 1 ≤ k ≤ m ≤ 50 000이다. 부분문제의 입력에는 다음과 같은 추가 제약이 있다.
힌트
첫 번째 차관은 선로 1–3, 2–3, 3–4, 4–5가 필요하다고 생각한다. 두 번째 차관은 선로 3–4와 4–6을, 세 번째 차관은 선로 2–3만 필요하다고 본다. 선로 2–3과 3–4는 차관 두 명 이상이 필요하다고 본 선로이다.