685 . 公會合併

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

apcsc apcsc-ds

Description

一款「切小黃瓜」的遊戲開服不到一個月就開始面臨玩家流失的問題。遊戲裡的公會不斷合併。
桃子是這款遊戲的死忠粉絲，為了研究各個公會之間的關係，它想要知道任兩個公會在何時初次被合併成同一個公會。

Input Format

輸入第一行有兩個數字 $N, Q$，分別代表公會初始數量與操作的次數。
接下來有 $Q$ 行，每行有一筆操作，操作格式如下：

  1. 1 u v: 包含 $u$ 的整個公會與包含 $v$ 的整個公會合併
  2. 2 u v: 詢問 $u$ 公會與 $v$ 公會何時第一次被合併成同一公會
  • $1 \leq N, Q \leq 2 \cdot 10^ 5$
  • $1 \leq u, v \leq N$

Output Format

請輸出詢問次數的行數。每行包含一個數字，代表兩公會第一次成為同一公會的時間。(若兩公會於操作 $1$ 初次成為同一公會，輸出 1)
若兩個公會在詢問當下並不是同一公會，輸出 -1。

Sample Input 1

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

Sample Output 1

0
-1
4

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~11 無額外限制 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
Submit
Back to Top