Description

As we all know, Xiao Z lives in a mansion with $n$ rooms, connected by $m$ passages (the house is connected).

One day, while Xiao Z was away, Xiao Y decided to pay a secret visit and planned to visit each room at least once. Unfortunately, $k$ of the rooms are equipped with sensors, each of which returns a message the first time someone visits it.

When Xiao Z came home, he found that Xiao Y had been there, and Xiao Y truthfully told him that he visited each room at least once.

However, after carefully examining the order in which the sensors returned messages, Xiao Z suspected that some sensors might have delayed reporting.

To test his hypothesis, including that time, he had Xiao Y come to his house a total of $q$ times. He wants to determine whether the order of sensor messages for each visit could possibly occur, and asks you to help.

Input Format

The first line contains four integers $n, m, k, q$.

Each of the next $m$ lines contains two integers $x, y$, indicating that rooms $x$ and $y$ are connected by a bidirectional passage.

Each of the next $q$ lines contains $k$ integers, representing the indices of the rooms with sensors, in the order their messages were returned.

Output Format

Output $q$ lines. Each line contains the string Yes or No, indicating whether the given order of sensor messages could occur.

5 5 3 2
1 2
2 3
3 1
1 4
4 5
4 2 1
4 1 2

No
Yes

Hint

Sample explanation:

For the first query, $4 \to 2$ must pass through $1$, so the answer is No.

For the second query, the path $4 \to 5 \to 4 \to 1 \to 3 \to 2 \to 1 \to 3$ matches the given record, so the answer is Yes.

Constraints:

For $10\%$ of the testdata, $n \le 2$.

For $30\%$ of the testdata, $n \le 3$.

For $60\%$ of the testdata, $n \le 10000$, $m \le 20000$, $k \le 10$.

For $100\%$ of the testdata, $1 \le k \le n \le 10^5$, $1 \le m \le 2 \times 10^5$, $1 \le q \le 5$, $1 \le x, y \le n$, $x \ne y$.

Translated by ChatGPT 5