[BalticOI 2017] Railway

题目背景

Bergen 基础设施建设部在一年前就有了把所有的城市用道路连起来的想法。 可惜的是,过了一年了,这个计划烂尾了。 所以,基础设施建设部部长就准备重启这个计划,然后把它搞得简单亿点。

题目描述

原定的计划是有 $n$ 个城市用 $n-1$ 个道路连起来。 现在有 $m$ 个副部长,每个副部长都认为有一些城市是必须连起来的。 比如说这个副部长想把 $a$ 和 $c$ 连起来,有两条道路 $a - b$ 和 $b - c$,那么副部长的要求等价过来就是选择这两条道路。 现在要找出几条道路是至少 $k$ 个副部长选择的。 部长就找到了您,想让您找出这几条道路。

输入输出格式

输入格式


第一行三个整数 $n,m,k$ 代表城市数,副部长数和最少需要满足多少个副部长。 接下来 $n-1$ 行每行两个整数 $a_i$ 和 $b_i$ 代表第 $i$ 条道路是 $a_i$ 和 $b_i$ 之间的。 这 $n-1$ 个道路的编号就是 $1$ 到 $n-1$。 接下来 $m$ 行首先一个整数 $s_i$ 代表这个副部长觉得有 $s_i$ 个城市需要相连,接下来 $s_i$ 个整数代表副部长觉得哪些城市需要相连。

输出格式


第一行一个整数 $r$ 代表至少满足 $k$ 个副部长的道路有多少个。 第二行 $r$ 个整数代表要搭建编号为哪些的道路的升序排列。

输入输出样例

输入样例 #1

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

输出样例 #1

2
2 3

说明

#### 样例说明 $3$ 个副部长的要求如下: - $1-3,2-3,3-4,4-5$ - $3-4,4-6$ - $2-3$ 至少满足 $2$ 个副部长的道路为 $2$ 号和 $3$ 号。 #### 数据范围 **本题采用捆绑测试。** - Subtask 1(8 pts):$n \le 10^4$,$\sum s_i \le 2 \times 10^3$。 - Subtask 2(15 pts):$n \le 10^4$,$m \le 2 \times 10^3$。 - Subtask 3(7 pts):每个城市最多是 $2$ 条道路的端点。 - Subtask 4(29 pts):$k=m$,$s_i=2$。 - Subtask 5(16 pts):$k=m$。 - Subtask 6(25 pts):无特殊限制。 对于 $100\%$ 的数据,$2 \le s_i \le n \le 10^5$,$1 \le k \le m \le 5 \times 10^4$,$\sum s_i \le 10^5$。 #### 说明 **翻译自 [BOI 2017 D1](https://boi.cses.fi/files/boi2017_day1.pdf) T2 Railway。** 翻译者:@[一只书虫仔](https://www.luogu.com.cn/user/114914)。 应扶咕咕的要求已经删减 $1 \sim 5$ 子任务中的部分数据,保留了 $6$ 子任务中的极限数据。