Gegeben ist ein ungerichteter Graph mit $n$ Knoten und $m$ Kanten. Der Graph enthält weder Selbstschleifen noch Mehrfachkanten und ist nicht notwendigerweise zusammenhängend. Die Knoten sind von $1$ bis $n$ nummeriert.
Es gibt $q$ Anfragen. Jede Anfrage ist ein Paar $(x, y)$. Du musst bestimmen, ob der Abstand zwischen $x$ und $y$ echt größer als $20\,000$ ist oder nicht.
Der Abstand zwischen zwei Knoten ist die Anzahl der Kanten auf einem kürzesten Pfad zwischen ihnen. Wenn es keinen kürzesten Pfad gibt, gilt der Abstand als $+\infty > 20\,000$.
Eingabe
Die erste Zeile enthält drei ganze Zahlen $n$, $m$ und $q$ ($1 \le n \le 10^5$, $0 \le m \le 3 \cdot 10^5$, $1 \le q \le 3 \cdot 10^5$).
Darauf folgen $m$ Zeilen mit jeweils zwei ganzen Zahlen $u_i$ und $v_i$, welche die Kanten darstellen ($1 \le u_i < v_i \le n$, keine zwei Kanten stimmen überein).
Danach folgen $q$ Zeilen mit jeweils zwei ganzen Zahlen $x_i$ und $y_i$ ($1 \le x_i, y_i \le n$, $x_i$ und $y_i$ können übereinstimmen).
Ausgabe
Gib $q$ Zeilen aus, jede entweder mit „YES“ oder „NO“: die Antworten auf die Anfragen.
Beispiel
Beispieleingabe 1
10 5 10 1 2 1 7 3 10 4 10 5 6 3 3 5 6 5 2 10 6 9 4 6 6 1 7 10 1 10 5 8 7
Beispielausgabe 1
NO NO YES YES YES NO NO YES YES YES
Hinweis
Im Beispiel gibt es nur $10$ Knoten im Graphen, sodass wir prüfen, ob sich die Knoten in verschiedenen Zusammenhangskomponenten befinden oder nicht.