Ildar quyết định theo đuổi hội họa trừu tượng. Làm nền cho bức tranh của mình, anh ấy lấy một cây có gốc với $n$ đỉnh: một đồ thị không có chu trình, trong đó đỉnh số 1 được chọn làm gốc. Gốc không có cha, và với mọi đỉnh $u \ge 2$, đỉnh đầu tiên trên đường đi từ $u$ đến gốc được gọi là cha của đỉnh $u$, ký hiệu là $p_u$. Các đỉnh có cha là đỉnh $v$ được gọi là con của đỉnh $v$. Nếu một đỉnh không có con, nó được gọi là lá. Dữ liệu đảm bảo rằng gốc có ít nhất hai con.
Hãy thực hiện duyệt theo chiều sâu (DFS) trên cây: chúng ta thăm gốc, sau đó lần lượt thăm các cây con của các con của nó theo cùng một cách. Các đỉnh của cây được đánh số theo thứ tự của quá trình duyệt theo chiều sâu này. Do đó, với mỗi $i$ từ 1 đến $n$, các số đỉnh trong cây con của đỉnh $i$ tạo thành một tập hợp các số nguyên liên tiếp.
Giả sử cây có $m$ lá. Ildar viết các số của chúng theo thứ tự tăng dần, thu được một dãy số $l_1 < l_2 < \dots < l_m$, và nối bằng một cạnh tất cả các cặp lá có dạng $(l_j, l_{j+1})$, đồng thời nối hai đỉnh $l_m$ và $l_1$. Chu trình $l_1 \to l_2 \to \dots \to l_m \to l_1$ được thêm vào đồ thị được gọi là chu trình ngoài.
Ildar vẽ đồ thị thu được lên một mặt phẳng như sau: anh ấy biểu diễn chu trình ngoài thành một đường tròn, dọc theo đó các lá $l_1, l_2, \dots, l_m$ nằm ngược chiều kim đồng hồ, và các cung của đường tròn giữa các đỉnh kề nhau biểu diễn các cạnh của chu trình ngoài. Các đỉnh còn lại của cây được biểu diễn thành các điểm phân biệt nằm bên trong đường tròn này. Các cạnh của cây được biểu diễn thành các đoạn thẳng giữa các đỉnh, và các đỉnh cùng các cạnh được bố trí sao cho các đoạn thẳng của các cạnh không có điểm trong chung. Hình dưới đây cho thấy một ví dụ về hình vẽ cây.
Trong hình vẽ của Ildar, phần mặt phẳng bên trong đường tròn của chu trình ngoài được chia thành $m$ vùng được giới hạn bởi các cạnh của đồ thị. Chúng ta sẽ gọi các vùng này là mặt. Hai mặt phân biệt được gọi là kề nhau nếu chúng có chung một cạnh. Ví dụ, trong hình trên, có 5 mặt, hãy ký hiệu chúng là $\Gamma_1, \Gamma_2, \Gamma_3, \Gamma_4$ và $\Gamma_5$.
Các mặt kề nhau trong hình trên là các cặp mặt $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_5)$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_4)$, $(\Gamma_2, \Gamma_5)$, $(\Gamma_3, \Gamma_4)$ và $(\Gamma_4, \Gamma_5)$.
Để hoàn thành bức tranh của mình, Ildar dự định tô mỗi mặt bằng một trong $k$ màu. Một cách tô màu được gọi là đúng nếu các mặt kề nhau được tô bằng các màu khác nhau. Ildar gọi tiềm năng của hình vẽ là phần dư của phép chia số lượng cách tô màu đúng khác nhau cho $10^9 + 7$.
Sau khi đánh giá tiềm năng của hình vẽ ban đầu, Ildar thực hiện $q$ thao tác với các cạnh của đồ thị đã vẽ. Xét thao tác thứ $i$, được xác định bởi một số $v_i$ và được thực hiện trên cạnh cây nối hai đỉnh $v_i$ và $p_{v_i}$. Nếu cạnh này hiện đang được vẽ trên hình, Ildar xóa cạnh đó khỏi hình vẽ; nếu cạnh này không có trên hình vẽ, nó sẽ được vẽ lại. Sau mỗi lần thay đổi, tập hợp các mặt trong hình vẽ có thể thay đổi: hai mặt có thể hợp nhất khi một cạnh bị xóa, hoặc một mặt có thể tách thành hai khi một cạnh được vẽ. Ví dụ, nếu chúng ta xóa cạnh $8 - 9$ trong hình trên, thì các mặt $\Gamma_4$ và $\Gamma_5$ sẽ hợp nhất thành một mặt $\Gamma_{4+5}$.
Khi đó, các cặp mặt kề nhau trong hình vẽ là $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_{4+5})$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_{4+5})$ và $(\Gamma_3, \Gamma_{4+5})$.
Sau mỗi thao tác, cần xác định lại tiềm năng của hình vẽ: phần dư của phép chia số lượng cách tô màu đúng các mặt với tối đa $k$ màu cho $10^9 + 7$.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa một số nguyên $t$ ($1 \le t \le 10\,000$) — số lượng bộ dữ liệu. Tiếp theo là mô tả của $t$ bộ dữ liệu.
Dòng đầu tiên của mỗi bộ dữ liệu chứa ba số nguyên $n$, $k$ và $q$ ($3 \le n \le 10^6$, $2 \le k \le 10^9$, $0 \le q \le 300\,000$) — lần lượt là số đỉnh của cây, số lượng màu có sẵn và số thao tác được thực hiện.
Dòng thứ hai của mỗi bộ dữ liệu chứa các số $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), trong đó $p_i$ là cha của đỉnh $i$ trong cây. Dữ liệu đảm bảo rằng các đỉnh của cây được đánh số theo thứ tự duyệt theo chiều sâu và giá trị 1 xuất hiện ít nhất hai lần trong các giá trị $p_2, \dots, p_n$.
Sau đó là $q$ dòng, dòng thứ $i$ chứa số $v_i$ ($2 \le v_i \le n$) — tham số của thao tác thứ $i$.
Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^6$.
Dữ liệu đảm bảo rằng tổng của $q$ trên tất cả các bộ dữ liệu không vượt quá $300\,000$.
Dữ liệu ra
Với mỗi bộ dữ liệu, xuất ra $q + 1$ số nguyên, số đầu tiên phải bằng tiềm năng của hình vẽ ban đầu, và các số còn lại phải bằng tiềm năng của hình vẽ sau khi thực hiện mỗi thao tác.
Nhiệm vụ con
Ta định nghĩa chiều cao của một cây là số cạnh lớn nhất trên một đường đi đơn từ gốc đến bất kỳ đỉnh nào khác.
| Nhiệm vụ con | Điểm | $n$ | $k$ | $q$ | Ràng buộc bổ sung | Nhiệm vụ con yêu cầu |
|---|---|---|---|---|---|---|
| 1 | 6 | $n = 3$ | $k \le 4$ | $q \le 10$ | $t \le 100$, $p_2 = p_3 = 1$ | |
| 2 | 9 | $\sum n \le 1000$ | $q = 0$ | $p_i = 2 \cdot \lfloor \frac{i}{2} \rfloor - 1$, $n$ lẻ | ||
| 3 | 10 | $\sum n \le 1000$ | $\sum q \le 1000$ | $p_i = 1$ | 1 | |
| 4 | 4 | $n \le 9$ | $k \le 4$ | $q = 0$ | $t \le 100$ | |
| 5 | 3 | $n \le 9$ | $k \le 4$ | $q \le 10$ | $t \le 100$ | Chính nó, 4 |
| 6 | 2 | $\sum n \le 1000$ | $k = 2$ | $q = 0$ | ||
| 7 | 11 | $\sum n \le 1000$ | $q = 0$ | 2, 4, 6 | ||
| 8 | 15 | $\sum n \le 1000$ | $\sum q \le 1000$ | Chính nó, 1–7 | ||
| 9 | 4 | $\sum n \le 5000$ | $\sum q \le 5000$ | Chính nó, 1–8 | ||
| 10 | 3 | $\sum n \le 10\,000$ | $\sum q \le 10\,000$ | Chính nó, 1–9 | ||
| 11 | 6 | $\sum n \le 100\,000$ | $\sum q \le 5000$ | Chính nó, 1–9 | ||
| 12 | 7 | $\sum n \le 100\,000$ | $\sum q \le 100\,000$ | chiều cao tối đa 20 | Chính nó, 1, 4, 5 | |
| 13 | 14 | $\sum n \le 100\,000$ | $\sum q \le 100\,000$ | Chính nó, 1–12 | ||
| 14 | 3 | $\sum n \le 300\,000$ | $\sum q \le 300\,000$ | Chính nó, 1–13 | ||
| 15 | 3 | $\sum n \le 1\,000\,000$ | $\sum q \le 300\,000$ | Chính nó, 1–14 |
Ví dụ
Dữ liệu vào 1
2 3 4 5 1 1 2 3 2 3 3 9 4 8 1 2 2 1 5 5 1 8 9 8 3 5 4 3 9 8
Dữ liệu ra 1
12 4 4 4 12 4 96 48 48 24 12 12 12 12 36