QOJ.ac

QOJ

Time Limit: 2.5 s Memory Limit: 1024 MB Total points: 100
[+11]

# 7869. 建设终末树

Statistics

小 C 和小 Y 种了一棵树 T=(V,E),她们希望把一个物品集合 S 中的所有物品都挂到树的节点上。物品 i 挂在的节点为 ai,两个物品可以挂在同一个节点。

小 Y 突发奇想,她定义了一个点集 V0V 的「导出」f(V0)TV0 中任意两点在树上最短路径的并,定义 fV 表示 f 的点集,fE 表示 f 的边集。

小 Y 给出了 q 个二元集合 (Vj,Sj),其中 VjV,SjS。她希望对于每个 j 都能满足 fE(Vj)fE({ak|kSj})=
Vj 的「导出」与 Sj 中所有物品所在结点的「导出」二者边集的交集为空。

“Y 你个笨蛋。”小 C 听了之后吐槽了一句,“你就没发现什么不对劲吗。”

于是小 C 补加了 m 个限制 AiV:对于物品 i,需要满足 aifV(Ai)

“现在没问题了。”小 C 和小 Y 说,“但是怎么挂呢?”

请你帮帮她们,判断能否把所有物品挂在树上,如果可以请输出任意一组方案。

输入格式

第一行三个整数 n,m,q 分别表示题面中的 |V|,|S|,q

接下来 n1 行,每行两个数 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

数据范围与约定

对于所有数据,满足 3n,m2000,0q5×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 分):无特殊限制。