Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100
Statistics

$n$개의 정점과 $m$개의 간선으로 이루어진 무방향 그래프가 있습니다. 이 그래프는 자기 루프나 중복 간선을 포함하지 않으며, 반드시 연결되어 있는 것은 아닙니다. 정점은 $1$부터 $n$까지 번호가 매겨져 있습니다.

$q$개의 쿼리가 주어집니다. 각 쿼리는 순서쌍 $(x, y)$입니다. 당신은 $x$와 $y$ 사이의 거리가 $20\,000$보다 엄격하게 큰지 아닌지를 판별해야 합니다.

두 정점 사이의 거리는 두 정점을 잇는 최단 경로에 포함된 간선의 개수입니다. 최단 경로가 존재하지 않는다면 거리는 $+\infty > 20\,000$인 것으로 간주합니다.

입력

첫 번째 줄에 세 정수 $n$, $m$, $q$($1 \le n \le 10^5$, $0 \le m \le 3 \cdot 10^5$, $1 \le q \le 3 \cdot 10^5$)가 주어집니다.

이어서 $m$개의 줄에 걸쳐 각 줄마다 간선을 나타내는 두 정수 $u_i$와 $v_i$($1 \le u_i < v_i \le n$, 어떤 두 간선도 겹치지 않음)가 주어집니다.

그다음 $q$개의 줄에 걸쳐 각 줄마다 두 정수 $x_i$와 $y_i$($1 \le x_i, y_i \le n$, $x_i$와 $y_i$는 같을 수 있음)가 주어집니다.

출력

쿼리의 답으로 각 줄에 "YES" 또는 "NO"를 $q$개의 줄에 걸쳐 출력합니다.

예제

예제 입력 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

예제 출력 1

NO
NO
YES
YES
YES
NO
NO
YES
YES
YES

노트

예제에서는 그래프의 정점이 $10$개뿐이므로, 사실상 두 정점이 서로 다른 연결 요소(connected component)에 속하는지 여부를 확인하는 것과 같습니다.

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.