TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

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

  1. 第 $x$ 個人和第 $y$ 個人認識了。 因為 JOI 高中裡面的人都很熱情,所以如果 $a, b$ 兩個人認識,那他們就會介紹所有自己的朋友給對方的所有朋友認識,進而形成更大的交友圈。
  2. 你忽然很想知道第 $x$ 個人和第 $y$ 個人認不認識。
  3. 你忽然很想知道第 $x$ 個人認識幾個人(包含他自己)。
  4. 你忽然很想知道現在有多少個朋友組合,也就是說存在多少 $i < j$,且第 $i, j$ 兩個人互相認識。

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

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)$ 個人認識幾個人(包含他自己)。
  4. 4 你忽然很想知道現在有多少個朋友組合,也就是說存在多少 $i < j$,且第 $i, j$ 兩個人互相認識。

註:每個人都認識自己。

Output Format

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

Sample Input 1

4 6
1 1 2
2 1 2
3 1
1 1 3
2 2 3
4

Sample Output 1

Yes
2
Yes
3

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