問題一覧 > 通常問題

No.2319 Friends+

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 82
作問者 : 👑 amentorimaru / テスター : tatyam cleantted
お気に入りにしたユーザー ProblemId : 9355 / 自分の提出
問題文最終更新日: 2023-05-10 22:26:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 390 (順位表) の他の問題:

Problem Statement

In a certain virtual space, there are $N$ Etowanyu-kun numbered $1,2,\dots,N$, and $N$ worlds numbered $1,2,\dots,N$. Initially, Etowanyu-kun $i$ is in world $P_i$.

In addition, there are $M$ bidirectional friend relationships among the Etowanyu-kun: Etowanyu-kun $A_i$ and Etowanyu-kun $B_i$ are friends with each other.

From now on, the Etowanyu-kun will travel between worlds using the join command described below. It's cute how they wander around.

Join command

When Etowanyu-kun $X$ uses the join command on Etowanyu-kun $Y$, the following happens.

  • If the following $2$ conditions are both satisfied, the join command succeeds, and Etowanyu-kun $X$ moves to the world where Etowanyu-kun $Y$ is.
    • Etowanyu-kun $X$ and Etowanyu-kun $Y$ are in different worlds.
    • At least one friend of Etowanyu-kun $X$ is in the world where Etowanyu-kun $Y$ is.
  • Otherwise, the join command fails, and Etowanyu-kun $X$ stays where it is.

You are given $Q$ join commands performed by the Etowanyu-kun, in order. The $i$-th command is that Etowanyu-kun $X_i$ joins Etowanyu-kun $Y_i$. Determine whether each command succeeds or fails.

Input

$N \ M$
$P_1 \ P_2 \ \dots P_N$
$A_1 \ B_1$
$A_2 \ B_2$
$\vdots$
$A_M \ B_M$
$Q$
$X_1 \ Y_1$
$X_2 \ Y_2$
$\vdots$
$X_Q \ Y_Q$

  • All input values are integers.
  • $1 \le N \le 2 \times 10^4$
  • $0 \le M \le \min(2 \times 10^5, N(N+1)/2)$
  • $1 \le Q \le 2 \times 10^5$
  • $1 \le A_i,B_i,X_i,Y_i,P_i \le N$
  • For $i \ne j$, $(A_i,B_i) \ne (A_j,B_j)$ and $(A_i,B_i) \ne (B_j,A_j)$.

Output

Print $Q$ lines. On the $i$-th line, print Yes if the $i$-th join command succeeds, and No if it fails.

Sample

Sample 1
Input
4 2
1 2 2 3
1 2
1 4
5
1 3
1 4
2 4
1 4
1 3
Output
Yes
Yes
Yes
No
No

Initially, Etowanyu-kun $1, 2, 3, 4$ are in worlds $1, 2, 2, 3$, respectively. Etowanyu-kun $1$ and Etowanyu-kun $2$ are friends with each other, and so are Etowanyu-kun $1$ and Etowanyu-kun $4$.

In the $1$-st command, Etowanyu-kun $1$ and Etowanyu-kun $3$ are not friends, but Etowanyu-kun $2$, who is in the same world as Etowanyu-kun $3$, is a friend of Etowanyu-kun $1$, so the join succeeds. Print Yes; the worlds of all the Etowanyu-kun become $2,2,2,3$, respectively.

In the $2$-nd command, Etowanyu-kun $1$ and Etowanyu-kun $4$ are friends, so the join succeeds. Print Yes; the worlds of all the Etowanyu-kun become $3,2,2,3$, respectively.

In the $3$-rd command, Etowanyu-kun $2$ and Etowanyu-kun $4$ are not friends, but Etowanyu-kun $1$, who is in the same world as Etowanyu-kun $4$, is a friend of Etowanyu-kun $2$, so the join succeeds. Print Yes; the worlds of all the Etowanyu-kun become $3,3,2,3$, respectively.

In the $4$-th command, Etowanyu-kun $1$ and Etowanyu-kun $4$ are friends, but they are in the same world, so the join fails. Print No.

In the $5$-th command, there are no friends of Etowanyu-kun $1$ in the world where Etowanyu-kun $3$ is, so the join fails. Print No.

Sample 2
Input
1 1
1
1 1
1
1 1
Output
No

In this virtual space, it seems possible to be friends with oneself.

Etowanyu-kun $1$ tries to join Etowanyu-kun $1$, but the join fails because they are in the same world.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。