#P6572. [BalticOI 2017] Railway

[BalticOI 2017] Railway

题目背景

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

题目描述

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

输入格式

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

输出格式

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

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

提示

样例说明

33 个副部长的要求如下:

  • 13,23,34,451-3,2-3,3-4,4-5
  • 34,463-4,4-6
  • 232-3

至少满足 22 个副部长的道路为 22 号和 33 号。

数据范围

本题采用捆绑测试。

  • Subtask 1(8 pts):n104n \le 10^4si2×103\sum s_i \le 2 \times 10^3
  • Subtask 2(15 pts):n104n \le 10^4m2×103m \le 2 \times 10^3
  • Subtask 3(7 pts):每个城市最多是 22 条道路的端点。
  • Subtask 4(29 pts):k=mk=msi=2s_i=2
  • Subtask 5(16 pts):k=mk=m
  • Subtask 6(25 pts):无特殊限制。

对于 100%100\% 的数据,2sin1052 \le s_i \le n \le 10^51km5×1041 \le k \le m \le 5 \times 10^4si105\sum s_i \le 10^5

说明

翻译自 BOI 2017 D1 T2 Railway。
翻译者:@一只书虫仔

应扶咕咕的要求已经删减 151 \sim 5 子任务中的部分数据,保留了 66 子任务中的极限数据。