P2189 Xiao Z's Sensors

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.

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 $q$ lines. Each line contains the string `Yes` or `No`, indicating whether the given order of sensor messages could occur.

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