Sensor Report Order Verification

In this problem, you are given an undirected connected graph representing the rooms and corridors of a mansion. The mansion has n rooms and m corridors. In addition, k rooms are equipped with sensors. When a visitor tours the mansion, he visits every room at least once. The sensors record the time of the first visit to the room in which they are installed. However, due to suspected delays in the reporting, the owner wants to verify whether a given order of sensor reports is feasible – that is, whether there exists a walk (with revisits allowed) that covers all rooms, and such that the order in which the sensors are triggered (i.e. the first time the sensor‐rooms are visited) is exactly the given order.

It can be shown that for any connected undirected graph and for any permutation of a subset of vertices, there always exists a walk that visits every vertex at least once and that realizes that permutation as the order of the first visits to the sensor‐equipped rooms. (Formally, for any graph \(G=(V,E)\) which is connected, and for any ordering \(P = [s_1, s_2, \dots, s_k]\) of a subset \(S \subseteq V\), one can construct a walk \(W\) (vertices may appear multiple times in \(W\)) such that every vertex is visited at least once and the first occurrences of the vertices in \(S\) are exactly in the order \(s_1, s_2, \dots, s_k\).)

Your task is to simply decide, for each of the q rounds, whether the reported sensor order is possible. As the above fact holds, the answer for every round will be YES.

inputFormat

The input begins with a line containing four integers \(n\), \(m\), \(k\), and \(q\) \( (1 \leq n, m \leq 10^5,\; 1 \leq k \leq n,\; 1 \leq q \leq 10^5)\), representing the number of rooms, corridors, sensor‐equipped rooms, and rounds (visits) respectively.

The next \(m\) lines each contain two integers \(u\) and \(v\) \(1 \le u,v \le n\) indicating that there is an undirected corridor between rooms \(u\) and \(v\). It is guaranteed that the graph is connected.

Then follow \(q\) rounds. Each round is described by a line containing k distinct integers. These represent a permutation of the sensor‐equipped rooms, i.e. the order in which the sensors reported (the order of the first visits to these rooms).

outputFormat

For each round, output a single line containing YES if the reported sensor order is possible, or NO if it is not.

Note: Based on the fact mentioned in the problem description, the answer is always YES for a connected undirected graph.

sample

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

YES
YES