C'è un grafo non orientato con $n$ vertici e $m$ archi. Il grafo non contiene cappi o archi paralleli e non è necessariamente connesso. I vertici sono numerati da $1$ a $n$.
Ci sono $q$ query. Ogni query è una coppia $(x, y)$. Devi determinare se la distanza tra $x$ e $y$ è strettamente maggiore di $20\,000$ oppure no.
La distanza tra due vertici è il numero di archi su un cammino minimo tra di essi. Se non esiste alcun cammino, la distanza è considerata pari a $+\infty > 20\,000$.
Input
La prima riga contiene tre interi $n$, $m$ e $q$ ($1 \le n \le 10^5$, $0 \le m \le 3 \cdot 10^5$, $1 \le q \le 3 \cdot 10^5$).
Seguono poi $m$ righe, ciascuna contenente due interi $u_i$ e $v_i$, che rappresentano gli archi ($1 \le u_i < v_i \le n$, nessun arco coincide con un altro).
Dopodiché seguono $q$ righe, ciascuna contenente due interi $x_i$ e $y_i$ ($1 \le x_i, y_i \le n$, $x_i$ e $y_i$ possono coincidere).
Output
Stampa $q$ righe, ciascuna con "YES" oppure "NO": le risposte alle query.
Esempio
Input di esempio 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
Output di esempio 1
NO NO YES YES YES NO NO YES YES YES
Nota
Nell'esempio ci sono solo $10$ vertici nel grafo, quindi stiamo semplicemente verificando se i vertici si trovano in componenti connesse diverse oppure no.