QOJ.ac

QOJ

Time Limit: 2.5 s Memory Limit: 1024 MB Total points: 100

# 7869. 建设终末树

Statistics

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

小 Y 突发奇想,她定义了一个点集 $ V_0\subseteq V $ 的「导出」$ f(V_0)\subseteq T $ 为 $ V_0 $ 中任意两点在树上最短路径的并,定义 $ f_V $ 表示 $ f $ 的点集,$ f_E $ 表示 $ f $ 的边集。

小 Y 给出了 $ q $ 个二元集合 $ (V_j, S_j) $,其中 $ V_j\subseteq V, S_j\subseteq S $。她希望对于每个 $ j $ 都能满足 $ f_E(V_j)\cap f_E(\{a_k | k\in S_j\}) = \varnothing $。
即 $ V_j $ 的「导出」与 $ S_j $ 中所有物品所在结点的「导出」二者边集的交集为空。

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

于是小 C 补加了 $ m $ 个限制 $ A_i\subseteq V $:对于物品 $ i $,需要满足 $ a_i\in f_V(A_i) $。

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

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

输入格式

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

接下来 $ n-1 $ 行,每行两个数 $ u,v $,表示树上有一条 $ (u,v) $ 的边。

接下来 $ m $ 行,第 $ i $ 行第一个整数表示 $ |A_i| $,接下来 $ |A_i| $ 个整数表示 $ A_i $ 中每个点的编号。

接下来 $ 2q $ 行,每两行表示一个限制。 + 第 $ j $ 个限制的第一行第一个整数表示 $ |V_j| $,接下来 $ |V_j| $ 个整数表示 $ V_j $ 中的元素。 + 第 $ j $ 个限制的第二行第一个整数表示 $ |S_j| $,接下来 $ |S_j| $ 个整数表示 $ S_j $ 中的元素。

输出格式

如果无解,输出 -1,否则输出一行 $ m $ 个整数,第 $ i $ 个整数表示物品 $ i $ 所挂节点的编号,即题面中说的 $ a_i $。

样例输入 #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\leq n, m\leq 2000, 0\leq q\leq 5\times 10^5, 0\leq \sum |V_j|,\sum |S_j|\leq 5\times 10^5, 2\leq |V_j|,|S_j|\leq \min(n, m, 50) $。

  • 子任务 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 分):无特殊限制。