Hay un grafo no dirigido con $n$ vértices y $m$ aristas. El grafo no contiene bucles ni aristas paralelas y no es necesariamente conexo. Los vértices están numerados de $1$ a $n$.
Hay $q$ consultas. Cada consulta es un par $(x, y)$. Debes determinar si la distancia entre $x$ e $y$ es estrictamente mayor que $20\,000$ o no.
La distancia entre dos vértices es el número de aristas en un camino más corto entre ellos. Si no existe ningún camino entre ellos, se considera que la distancia es $+\infty > 20\,000$.
Entrada
La primera línea contiene tres enteros $n$, $m$ y $q$ ($1 \le n \le 10^5$, $0 \le m \le 3 \cdot 10^5$, $1 \le q \le 3 \cdot 10^5$).
A continuación siguen $m$ líneas, cada una con dos enteros $u_i$ y $v_i$, que representan las aristas ($1 \le u_i < v_i \le n$, no hay dos aristas que coincidan).
Después siguen $q$ líneas, cada una con dos enteros $x_i$ e $y_i$ ($1 \le x_i, y_i \le n$, $x_i$ e $y_i$ pueden coincidir).
Salida
Imprime $q$ líneas, cada una con "YES" o "NO": las respuestas a las consultas.
Ejemplo
Entrada de ejemplo 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
Salida de ejemplo 1
NO NO YES YES YES NO NO YES YES YES
Nota
En el ejemplo, solo hay $10$ vértices en el grafo, por lo que estamos comprobando si los vértices están en diferentes componentes conexas o no.