문제
몇 년 전, 베르겐 인프라부는 새로운 철도 네트워크 계획을 세웠다. 이 네트워크는 n개의 동네를 n−1개의 철도 노선으로 연결해 모든 동네 간에 경로가 존재하도록 설계되었다. 계획된 노선은 1부터 n−1까지의 번호로 식별된다.
세월이 흘러 새 선거가 다가왔지만, 철도 네트워크는 아직 설계도 위에만 존재한다. 이에 인프라부 장관은 계획의 일부라도 건설하기로 한다. 그는 m명의 부장관에게 자신들이 연결되어야 한다고 생각하는 동네를 선택하도록 요청했다. 그 결과, 각 부장관은 필요한 철도 노선의 목록을 제출했다.
부장관이 a₁, ..., aₛ 동네가 연결되어야 한다고 생각한다면, 그가 생각하는 필요한 철도 노선은 aᵢ에서 aⱼ까지의 모든 계획된 경로 상의 노선이다(단, 1 ≤ i < j ≤ s).
장관은 모든 부장관의 목록을 받은 후, 적어도 k명의 부장관이 요청한 철도 노선을 우선적으로 건설하기로 한다.
당신의 과제는 이러한 노선들의 목록을 준비하는 것이다.
입력
입력은 다음과 같은 형식으로 주어진다:
첫 번째 줄에 세 정수 n, m, k가 주어진다.
다음 n−1개의 줄에는 철도 계획이 주어지며, i번째 줄에는 두 정수 aᵢ, bᵢ가 주어진다(1 ≤ aᵢ, bᵢ ≤ n, aᵢ ≠ bᵢ). 이는 i번째 노선이 동네 aᵢ와 bᵢ를 연결함을 나타낸다.
이후 m개의 줄에는 부장관들이 선택한 동네가 주어지며, i번째 줄은 정수 sᵢ로 시작하며, 이는 i번째 부장관이 선택한 동네의 개수를 나타낸다. 이어서 sᵢ개의 정수가 주어지며, 이는 해당 부장관이 선택한 동네를 나타낸다.
[제약 조건]
항상 2 ≤ sᵢ ≤ n ≤ 100,000, S ≤ 100,000, 1 ≤ k ≤ m ≤ 50,000을 만족한다.
추가적인 서브태스크 조건이 있을 수 있다.
출력
출력은 다음과 같은 형식으로 작성한다:
첫 번째 줄에 한 정수 r을 출력한다. 이는 적어도 k명의 부장관이 요청한 철도 노선의 개수를 나타낸다.
두 번째 줄에는 r개의 노선 번호를 오름차순으로 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 8점 | |
| #2 | 15점 | |
| #3 | 7점 | 각 동네는 최대 2개의 계획된 노선의 종착지다. |
| #4 | 29점 | |
| #5 | 16점 | |
| #6 | 25점 | 추가 제약 조건 없음 |
예제1
632
13
23
34
64
45
41325
263
232
2
23
1번 부장관은 노선 1-3, 2-3, 3-4, 4-5를 필요하다고 생각한다.
2번 부장관은 노선 3-4와 4-6을, 3번 부장관은 노선 2-3만을 필요하다고 본다.
따라서, 적어도 두 부장관이 필요하다고 한 노선은 2-3과 3-4이다.