682 . JOI君的朋友

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

joycewang

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

55.0% (11/20)

Tags

apcsc apcsc-ds

Description

在大 JOI 高中裡面有 $N$ 個人，裡面的社交關係錯綜複雜。
已知最一開始的時候，這 $N$ 個人兩兩不認識。
在接下來的 $M$ 天之中，每天都有一些事情發生。

  1. 第 $x$ 個人和第 $y$ 個人認識了。 因為 JOI 高中裡面的人都很熱情，所以如果 $a, b$ 兩個人認識，那他們就會介紹所有自己的朋友給對方的所有朋友認識，進而形成更大的交友圈。
  2. 你忽然很想知道第 $x$ 個人和第 $y$ 個人認不認識。
  3. 你忽然很想知道第 $x$ 個人認識幾個人（包含他自己）。

請你在第 2, 3 種事件時，輸出你想要知道的資訊！

Input Format

輸入第一行有兩個正整數 $N, M(N \le 10^ 6, M \le 10^ 6)$ 以空白隔開。
第二行開始有 $M$ 行，每行都會是底下三種的其中一種

  1. 1 x y 代表 $x, y(1 \le x, y \le N)$ 今天突然認識了。（保證他們以前絕對不認識）。
  2. 2 x y 代表你忽然很想知道第 $x(1 \le x \le N)$ 個人和第 $y(1 \le y \le N)$ 個人認不認識。
  3. 3 x 你忽然很想知道第 $x(1 \le x \le N)$ 個人認識幾個人（包含他自己）。

註：每個人都認識自己。

Output Format

遇到第 2 種事件時，如果兩人認識請輸出一行 Yes 不然請輸出一行 No。
遇到第 3 種事件時，請輸出一行整數代表答案。

Sample Input 1

4 5
1 1 2
2 1 2
3 1
1 1 3
2 2 3

Sample Output 1

Yes
2
Yes

Hints

Problem Source

經典題

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~22 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
Submit
Back to Top