On considère un graphe non orienté comportant $n$ sommets et $m$ arêtes. Le graphe ne contient ni boucles ni arêtes multiples et n'est pas nécessairement connexe. Les sommets sont numérotés de $1$ à $n$.
Il y a $q$ requêtes. Chaque requête est une paire $(x, y)$. Vous devez déterminer si la distance entre $x$ et $y$ est strictement supérieure à $20\,000$ ou non.
La distance entre deux sommets est le nombre d'arêtes sur un plus court chemin les reliant. S'il n'existe aucun chemin entre eux, la distance est considérée comme étant $+\infty > 20\,000$.
Entrée
La première ligne contient trois entiers $n$, $m$ et $q$ ($1 \le n \le 10^5$, $0 \le m \le 3 \cdot 10^5$, $1 \le q \le 3 \cdot 10^5$).
Suivent ensuite $m$ lignes, contenant chacune deux entiers $u_i$ et $v_i$, représentant les arêtes ($1 \le u_i < v_i \le n$, deux arêtes ne coïncident jamais).
Après cela suivent $q$ lignes, contenant chacune deux entiers $x_i$ et $y_i$ ($1 \le x_i, y_i \le n$, $x_i$ et $y_i$ peuvent coïncider).
Sortie
Affichez $q$ lignes, chacune contenant soit « YES », soit « NO » : les réponses aux requêtes.
Exemple
Exemple d'entrée 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
Exemple de sortie 1
NO NO YES YES YES NO NO YES YES YES
Note
Dans l'exemple, il n'y a que $10$ sommets dans le graphe, nous vérifions donc simplement si les sommets appartiennent à des composantes connexes différentes ou non.