Universal Cup Judging System

Universal Cup

Límite de tiempo: 3.0 s Límite de memoria: 1024 MB Puntuación total: 100
Estadísticas

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.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.