E. Evil Problemsetters 2
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Teamscode's problemsetters have become evil! They have trapped you in a maze of $$$N$$$ rooms with $$$E$$$ bidirectional corridors, with at most one corridor between any two distinct rooms and no corridor leading from a room back to itself. Each room is painted with one of $$$L$$$ colors, and every color appears on at least one room. The maze has a peculiar structure: any two rooms of the same color always have the exact same multiset of neighboring room colors.

You don't know where you are or what colors mark the exits. You are given $$$Q$$$ scenarios to handle. In each scenario, you are told your starting room $$$v$$$ and a set of $$$l$$$ exit colors. Find the minimum number of corridors you must traverse to reach a room painted with one of the exit colors, or $$$-1$$$ if no such room is reachable from $$$v$$$.

It is guaranteed that in each scenario, the color of room $$$v$$$ is not among the exit colors.

Input

The first line contains three integers $$$N$$$, $$$E$$$, and $$$L$$$ ($$$2 \le N \le 2 \cdot 10^5$$$, $$$1 \le E \le 4 \cdot 10^5$$$, $$$2 \le L \le 500$$$), the number of rooms, corridors, and colors.

The next $$$E$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$, $$$u \ne v$$$), describing a corridor between rooms $$$u$$$ and $$$v$$$. No two rooms are connected by more than one corridor. The maze is not necessarily connected.

The next line contains $$$N$$$ integers $$$c_1, c_2, \ldots, c_N$$$ ($$$1 \le c_i \le L$$$), where $$$c_i$$$ is the color of room $$$i$$$.

The next line contains a single integer $$$Q$$$ ($$$1 \le Q \le 2 \cdot 10^5$$$), the number of scenarios.

Each scenario consists of two lines:

  • A line with two integers $$$v$$$ and $$$l$$$ ($$$1 \le v \le N$$$, $$$1 \le l \lt L$$$), your starting room and the number of exit colors.
  • A line with $$$l$$$ distinct integers $$$a_1, a_2, \ldots, a_l$$$ ($$$1 \le a_i \le L$$$), the exit colors.

It is guaranteed that the color of room $$$v$$$ does not appear among the exit colors.

It is guaranteed that the sum of all $$$l$$$ values does not exceed $$$10^7$$$.

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$5$$$ points.

Tests $$$1-4$$$ satisfy $$$N,Q \le 1000$$$.

Tests $$$5-20$$$ satisfy no additional constraints.

Output

Output $$$Q$$$ integers, one per line. The $$$i$$$-th integer is the minimum number of corridors you must traverse to reach an exit room in the $$$i$$$-th scenario, or $$$-1$$$ if no exit room is reachable.

Example
Input
4 3 4
4 1
4 2
4 3
1 2 3 4
2
2 2
3 4
4 1
1
Output
1
1
Note

In the first scenario, you start in room $$$2$$$ and the exits are colors $$$\{3, 4\}$$$. The closest exit is room $$$4$$$, reached via $$$2 \to 4$$$, so the answer is $$$1$$$.

In the second scenario, you start in room $$$4$$$ and the exits are color $$$1$$$. The closest exit is room $$$1$$$, reached via $$$4 \to 1$$$, so the answer is $$$1$$$.

—

Problem Idea: Bryan Zhu

Problem Preparation: jay_jayjay

Occurrences: Novice E