P1551 Relatives

If a family is too large, it can be hard to determine whether two people are relatives. Given a kinship graph, determine whether any given pair of people are relatives.

Rules: If $x$ and $y$ are relatives, and $y$ and $z$ are relatives, then $x$ and $z$ are also relatives. If $x$ and $y$ are relatives, then all relatives of $x$ are also relatives of $y$, and all relatives of $y$ are also relatives of $x$.

The first line contains three integers $n,m,p$ ($n,m,p \le 5000$), representing that there are $n$ people, $m$ kinship relations, and $p$ queries. Each of the following $m$ lines contains two integers $M_i,M_j$ ($1 \le M_i,~M_j \le n$), indicating that $M_i$ and $M_j$ are relatives. Then the next $p$ lines each contain two integers $P_i,P_j$, asking whether $P_i$ and $P_j$ are relatives.

Output $p$ lines. Each line contains either `Yes` or `No`, indicating whether the answer to the $i$-th query is “are relatives” or “are not relatives.”

Translated by ChatGPT 5