Universal Cup Judging System

Universal Cup

実行時間制限: 3.0 s メモリ制限: 1024 MB 満点: 100
統計

給定一個有 $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$ 可能相同)。

輸出格式

輸出 $q$ 行,每行輸出「YES」或「NO」:代表各次詢問的答案。

範例

範例輸入 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$ 個頂點,因此我們實際上是在檢查這些頂點是否位於不同的連通分量中。

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.