在一個業界當中，存在 $\color{black}{n}$ 個人，而在一開始，每個人各自屬於自己的公司，每間公司一開始也只有 $1$ 個人。現在有 $\color{black}{q}$ 個事件，每個事件會照順序發生，而每個事件可能的類型為：
1. $\color{black}{u}$ 與 $\color{black}{v}$ 所在的公司進行合併，注意，若 $\color{black}{u}$ 與 $\color{black}{v}$ 原本就在同一個公司，則不會發生任何事情。
2. $\color{black}{u}$ 從原本的公司跳槽，跳槽至朋友 $\color{black}{v}$ 所在的公司，除 $\color{black}{u}$ 之外的所有人，所在的公司不變。
3. 請你查詢 $\color{black}{u}$ 所在的公司中，成員個數與成員編號之總合。
第一行有兩個正整數 $\color{black}{n}$、$\color{black}{q}$，代表有 $\color{black}{n}$ 個人與 $\color{black}{q}$ 個事件。接下來有 $\color{black}{q}$ 行，一行代表一個事件，每行的第一個數字 $\color{black}{t}$ 代表該事件是第 $\color{black}{t}$ 類事件：
• 若 $\color{black}{t= 1}$，則同一行會再有兩個正整數 $\color{black}{u}$、$\color{black}{v}$，代表 $\color{black}{u}$、$\color{black}{v}$ 兩人所在的公司合併。
• 若 $\color{black}{t= 2}$，則同一行會再有兩個正整數 $\color{black}{u}$、$\color{black}{v}$，代表 $\color{black}{u}$ 從原本的公司跳槽至朋友 $\color{black}{v}$ 所在的公司。
• 若 $\color{black}{t=3}$，則同一行會再有一個正整數 $\color{black}{u}$，代表要查詢在 $\color{black}{u}$ 所在的公司中，成員個數與成員編號之總合。
$\color{black}{1 \le n \le 10^5}$
$\color{black}{1 \le q \le 2 \times 10^5}$
$\color{black}{1 \le t \le 3}$
$\color{black}{1 \le u,v \le n}$
對於每個第 3 類的事件,輸出兩個正整數
5 7 1 1 2 2 3 4 1 3 5 3 4 2 4 1 3 4 3 3
3 12 3 7 2 8
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||