小 C 和小 Y 种了一棵树 T=(V,E),她们希望把一个物品集合 S 中的所有物品都挂到树的节点上。物品 i 挂在的节点为 ai,两个物品可以挂在同一个节点。
小 Y 突发奇想,她定义了一个点集 V0⊆V 的「导出」f(V0)⊆T 为 V0 中任意两点在树上最短路径的并,定义 fV 表示 f 的点集,fE 表示 f 的边集。
小 Y 给出了 q 个二元集合 (Vj,Sj),其中 Vj⊆V,Sj⊆S。她希望对于每个 j 都能满足 fE(Vj)∩fE({ak|k∈Sj})=∅。
即 Vj 的「导出」与 Sj 中所有物品所在结点的「导出」二者边集的交集为空。
“Y 你个笨蛋。”小 C 听了之后吐槽了一句,“你就没发现什么不对劲吗。”
于是小 C 补加了 m 个限制 Ai⊆V:对于物品 i,需要满足 ai∈fV(Ai)。
“现在没问题了。”小 C 和小 Y 说,“但是怎么挂呢?”
请你帮帮她们,判断能否把所有物品挂在树上,如果可以请输出任意一组方案。
输入格式
第一行三个整数 n,m,q 分别表示题面中的 |V|,|S|,q。
接下来 n−1 行,每行两个数 u,v,表示树上有一条 (u,v) 的边。
接下来 m 行,第 i 行第一个整数表示 |Ai|,接下来 |Ai| 个整数表示 Ai 中每个点的编号。
接下来 2q 行,每两行表示一个限制。 + 第 j 个限制的第一行第一个整数表示 |Vj|,接下来 |Vj| 个整数表示 Vj 中的元素。 + 第 j 个限制的第二行第一个整数表示 |Sj|,接下来 |Sj| 个整数表示 Sj 中的元素。
输出格式
如果无解,输出 -1
,否则输出一行 m 个整数,第 i 个整数表示物品 i 所挂节点的编号,即题面中说的 ai。
样例输入 #1
5 2 1
1 2
1 3
2 4
2 5
3 2 4 5
2 1 3
2 2 5
2 1 2
样例输出 #1
4 1
样例输入 #2
5 2 1
1 2
1 3
2 4
2 5
3 2 4 5
2 1 3
2 1 5
2 1 2
样例输出 #2
-1
数据范围与约定
对于所有数据,满足 3≤n,m≤2000,0≤q≤5×105,0≤∑|Vj|,∑|Sj|≤5×105,2≤|Vj|,|Sj|≤min。
- 子任务 1(10 分):树是一张菊花图,即它的直径长度为 2 。
- 子任务 2(15 分): n, m\leq 10, \sum |V_j|,\sum |S_j|\leq 20 。
- 子任务 3(20 分): n, m\leq 500, q\leq 5\times 10^3, |V_j|,|S_j|=2 ,树是一条链,即它的直径长度为 n-1 。
- 子任务 4(20 分): n, m\leq 500, \sum |V_j|,\sum |S_j|\leq 10^4 。
- 子任务 5(25 分): \sum |V_j|,\sum |S_j|\leq 10^5 。
- 子任务 6(10 分):无特殊限制。