這是一道互動題。

偉大的科學家欣準備建造強人工智慧隆統治世界。在輸入一些越南的演算法競賽題作為訓練集後，她發現隆自動生成了一個新的問題，並給出了一份解答。同時隆還將測試集中30%的輸入資料歸約到了這個問題。

欣連忙將這個問題抄錄如下：

給定一棵有根樹，你需要支援兩種操作

• 查詢樹鏈元素和
• 將一個點的父親改成另一個點

「這個問題並不強啊，為什麼能解決測試集中30%的問題呢？」欣心裡想。

在關閉訓練結果頁面前，欣突然發現，隆給出的這個問題中，資訊合併的代價並不是 $O(1)$ 的。

欣陷入了沉思，發現自己並不會這道題。

為了知道這題有多難，欣將這題放到了您的面前。

題目敘述

你需要維護一棵以 $1$ 為根的有根樹。這棵樹有 $n$ 個點。初始時對於所有 $2 \le i \le n$，點 $i$ 有個父親 $p_i$，保證 $p_i \lt i$。

一開始你有 $n$ 個集合 $\{1\},\{2\},\cdots,\{n\} $。對於任意兩個集合 $A$ 和 $B$，如果 $A \cap B=\varnothing$，那麼你可以透過一次操作，消耗 $|A|+|B|$ 的代價，獲得集合 $A \cup B$。

之後有 $q$ 次操作。每次操作有兩種類型

• 0 a b 記樹上 $a$ 到 $b$ 之間的路徑上的點構成的點集為 $S$。你需要將 $S$ 表示為 $\cup_{i=1}^{k}A_i$，需要滿足 $A_i$ 是你已經獲得的集合，且 $\forall i \neq j,A_i \cap A_j=\varnothing$。用 $(A_1,A_2,\cdots,A_k) $ 回答一次詢問的代價為 $k$。
• 1 a b 表示將點 $a$ 的父親改為 $b$，保證 $a \gt 1$，且修改後這 $n$ 個點仍構成一棵樹，但不保證 $a \gt b$。你可以在這次操作中新生成一些集合用以應對之後的詢問。

記你整個程式執行過程中消耗的總代價為 $C_1$，單次操作消耗代價最大值為 $C_2$。每個子任務會根據 $C_1,C_2$ 的大小按照一定方式給分。

實作細節

請確保你的程式開頭有 #include "long.h"。

標頭檔中定義了資料型別 infoset，用於儲存你獲得的集合。

該型別包括成員函式 size()，表示集合大小。標頭檔還為你提供了表示空集的常數 emptyset。

此外你還可以呼叫如下函式：

infoset merge(const infoset&A,const infoset&B);

• 以一定代價生成一個新集合 $A \cup B$
• 注意你可以多次重複生成同一個集合，並且需要多次計入代價

void report(infoset A);

• 你僅可以在查詢操作過程中呼叫該函式，表示你需要消耗 $1$ 的代價在最終的聯集中新增一個集合 $A$

你不需要，也不應該實作主函式。你需要實作如下幾個函式：

void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);

• 你可以在 $q$ 次操作開始前預處理一些資訊
• 在該函式中消耗的代價不會計入單次操作消耗代價最大值，但會計入整個程式執行過程中消耗的總代價
• id 表示子任務編號，n 表示總點數，q 表示總操作數
• dad 的大小為 $n-1$，dad[i] 表示初始時刻點 $i+2$ 的父親
• ve 的大小為 $n$，ve[i] 表示初始集合 $\{i+1\}$

void modify(int x,int y);

• 執行一次修改操作，將點 $x$ 的父親設為點 $y$

void ask(int x,int y);

• 執行一次查詢操作，詢問 $x$ 到 $y$ 的樹鏈資訊
• 你需要呼叫若干次 report 來回答詢問，本次詢問結束時互動函式庫會檢查你回報的所有集合 $A$ 是否滿足條件

評測時，互動函式庫會先呼叫 init 一次，然後呼叫 modify 和 ask 總共 $q$ 次。

本題保證樹的形態與執行的操作在互動開始之前已經完全確定，不會根據和你的程式的互動過程動態建構，因此題目中的互動操作都是確定性的，你不需要關心這些操作在互動函式庫中的具體實作。

評測時互動函式庫會使用特殊的實作方式，單個 infoset 型別的變數會恆定消耗 $8$ 位元組記憶體，請保證你的程式執行過程中沒有過多的 infoset 型別變數同時存在。

保證在呼叫次數限制下，互動函式庫執行所需的時間不超過 $2$ 秒；互動函式庫本身所消耗的記憶體不超過 $16$ MB。

測試程式方式

下發檔案中的 grader.cpp 是我們提供的互動函式庫參考實作，最終測試時所用的互動函式庫實作與該參考實作有所不同，因此選手的解法不應該依賴互動函式庫實作。

你需要使用如下命令編譯得到可執行程式：

g++ grader.cpp long.cpp -o long -static -O2 -std=c++14

對於編譯得到的可執行程式：

• 可執行檔將從標準輸入讀入以下格式的資料：

  • 第一行包含一個整數 $id$，表示子任務編號
  • 第二行包含兩個整數 $n,q$，表示總點數和總操作數
  • 第三行包含 $n-1$ 個整數，分別表示第 $2$ 至 $n$ 個點的父親節點編號
  • 接下來 $q$ 行，每行三個整數 $op,x,y$，描述一次操作。$op=0$ 表示這是一次詢問操作，$op=1$ 表示這是一次修改操作
• 讀入完成之後，互動函式庫將呼叫恰好一次函式 init 和 $q$ 次 modify 或 ask，用輸入的資料測試你的函式。程式正常執行後會輸出若干行，每行若干個數表示你對每次詢問操作給出的回答；最後一行會包括兩個整數 $W_1,W_2$，分別表示你程式執行消耗的總代價和單次操作消耗代價的最大值。

下發檔案中包括四組範例檔案，其中第四組範例滿足子任務二的特殊性質。測試範例時請忽略輸出檔案最後一行的比較情況，因為互動函式庫輸出的最後一行為程式執行代價而不是詢問操作的查詢結果。

子任務

本題首先會受到和傳統題相同的限制。例如編譯錯誤會導致整道題目得 $0$ 分，執行時錯誤、超過時間限制、超過空間限制等會導致相應測試點得 $0$ 分等。你只能存取自己定義的和互動函式庫給出的變數及其對應的記憶體空間，嘗試存取其他空間將可能導致編譯錯誤或執行錯誤。

在上述條件基礎上，在一個測試點中，若程式執行了非法的函式呼叫、沒有正常結束執行或詢問操作給出了錯誤回答，該測試點將會獲得 $0$ 分。否則，將根據你程式消耗的代價，有兩種評分方式：

• 評測方式一：若 $W_1 \gt 6 \cdot 10^8$，則該測試點得 $0$ 分；否則該測試點得分為 $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10} \times \text{該測試點所屬子任務分值}$
• 評測方式二：若 $W_2 \gt 2 \cdot 10^4$，則該測試點得 $0$ 分；否則該測試點得分為 $\frac{5000}{max(W_2,5000)} \times \text{該測試點所屬子任務分值}$

不同的子任務會使用不同的評測方式。一個子任務的得分為其中所有測試點得分的最小值。

資料範圍

保證對於所有測試點均有 $1 \le n,q \le 10^5$。

特殊性質：保證每個時刻除了 $1$ 號節點外每個節點至多只有一個兒子。

後記

欣發現您五個小時還是沒有做出本題，對隆的能力感到非常滿意。然而第二天早上起來後，欣突然發現隆做法的複雜度證明是錯的。