Xiao C and Xiao Y have planted a tree $T=(V, E)$, and they wish to hang all items in a set $S$ onto the nodes of the tree. Item $i$ is hung on node $a_i$, and multiple items can be hung on the same node.

Xiao Y has a sudden idea: she defines the "induced" subgraph $f(V_0) \subseteq T$ of a vertex set $V_0 \subseteq V$ as the union of all shortest paths between any two points in $V_0$ within the tree. Let $f_V$ denote the set of vertices in $f(V_0)$ and $f_E$ denote the set of edges in $f(V_0)$.

Xiao Y provides $q$ binary sets $(V_j, S_j)$, where $V_j \subseteq V$ and $S_j \subseteq S$. She requires that for every $j$, the condition $f_E(V_j) \cap f_E(\{a_k \mid k \in S_j\}) = \varnothing$ must be satisfied. That is, the intersection of the edge sets of the "induced" subgraph of $V_j$ and the "induced" subgraph of the nodes where all items in $S_j$ are located must be empty.

"You're such a fool, Y," Xiao C remarked after hearing this. "Didn't you notice something wrong?"

Consequently, Xiao C added $m$ constraints $A_i \subseteq V$: for item $i$, it must satisfy $a_i \in f_V(A_i)$.

"Now it's fine," Xiao C and Xiao Y said, "but how should we hang them?"

Please help them determine if it is possible to hang all items on the tree. If it is possible, output any valid assignment.

Input

The first line contains three integers $n, m, q$, representing $|V|$, $|S|$, and $q$ respectively.

The next $n-1$ lines each contain two integers $u, v$, representing an edge $(u, v)$ in the tree.

The next $m$ lines: the $i$-th line starts with an integer $|A_i|$, followed by $|A_i|$ integers representing the indices of the vertices in $A_i$.

The next $2q$ lines represent the constraints, with two lines per constraint:

• The first line of the $j$-th constraint starts with an integer $|V_j|$, followed by $|V_j|$ integers representing the elements in $V_j$.
• The second line of the $j$-th constraint starts with an integer $|S_j|$, followed by $|S_j|$ integers representing the elements in $S_j$.

Output

If there is no solution, output -1. Otherwise, output a single line containing $m$ integers, where the $i$-th integer represents the index of the node where item $i$ is hung, i.e., $a_i$ as described in the problem.

Examples

Input 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

Output 1

4 1

Input 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

Output 2

-1

Constraints

For all data, $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)$.

• Subtask 1 (10 points): The tree is a star graph, i.e., its diameter is $2$.
• Subtask 2 (15 points): $n, m \leq 10$, $\sum |V_j|, \sum |S_j| \leq 20$.
• Subtask 3 (20 points): $n, m \leq 500$, $q \leq 5 \times 10^3$, $|V_j|, |S_j| = 2$, the tree is a path, i.e., its diameter is $n-1$.
• Subtask 4 (20 points): $n, m \leq 500$, $\sum |V_j|, \sum |S_j| \leq 10^4$.
• Subtask 5 (25 points): $\sum |V_j|, \sum |S_j| \leq 10^5$.
• Subtask 6 (10 points): No special constraints.