#P2256. Same Group Query

    ID: 15533 Type: Default 1000ms 256MiB

Same Group Query

Same Group Query

There are $N$ ($2\leq N\leq 2\times 10^4$) participants. You are given their names. Then, you are given $M$ ($1\leq M\leq 10^6$) statements, each specifying that two students belong to the same group. Note that group membership is transitive; that is, if student A and student B are in the same group, and student B and student C are in the same group, then student A and student C are also in the same group.

After this, you will be given $K$ ($1\leq K\leq 10^6$) queries asking whether two given students are in the same group. If they are, output Yes.; otherwise, output No.

inputFormat

The input consists of several parts:

  1. The first line contains an integer $N$, the number of participants.
  2. The next $N$ lines each contain a string representing a participant's name.
  3. The following line contains an integer $M$, the number of statements.
  4. The next $M$ lines each contain two strings; each pair indicates that the two students are in the same group.
  5. The next line contains an integer $K$, the number of queries.
  6. The next $K$ lines each contain two strings representing the names of the students to be queried.

outputFormat

For each query, output a single line containing Yes. if the two students are in the same group, or No. otherwise.

sample

5
alice
bob
charlie
dave
eve
3
alice bob
bob charlie
dave eve
3
alice charlie
alice dave
dave eve
Yes.

No. Yes.

</p>