建设终末树 - Problem

小 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

样例输出 #1

4 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 分）：无特殊限制。

QOJ.ac

QOJ