Hội những người quan sát chim có \(n\) chi hội. Chi hội \(i\) có \(m_i\) thành viên và có một trưởng chi hội, cũng được gọi là viên chức \(i\). Trừ đúng một Chủ tịch, mỗi viên chức có đúng một người cố vấn; không viên chức nào là cố vấn trực tiếp hay gián tiếp của chính mình, nên quan hệ cố vấn tạo thành một cây có gốc là Chủ tịch.

Ảnh hưởng của một viên chức là tổng số thành viên của chi hội của họ và ảnh hưởng của tất cả các đệ tử trực tiếp. Tổng ảnh hưởng của Chủ tịch là \(M=\sum_i m_i\). Một viên chức là cấp cao nếu ảnh hưởng của họ ít nhất \(M/2\). Thủ quỹ là viên chức cấp cao có ảnh hưởng nhỏ nhất.

Sau trạng thái ban đầu, có \(q\) lần thay đổi người cố vấn. Hãy in Thủ quỹ ở trạng thái ban đầu và sau mỗi thay đổi.

Dữ liệu vào

Dòng đầu chứa \(n,q\). Mỗi trong \(n\) dòng tiếp theo chứa \(s_i,m_i\): \(s_i\) là người cố vấn của viên chức \(i\), và \(s_i=0\) khi \(i\) là Chủ tịch. Mỗi trong \(q\) dòng cuối chứa \(\hat{x}_j,\hat{z}_j\). Nếu \(t_{j-1}\) là Thủ quỹ trước thay đổi \(j\), đặt

Thay đổi \(j\) khiến \(z_j\) trở thành cố vấn mới của \(x_j\). Mọi thay đổi đã được bảo đảm hợp lệ: \(z_j\ne x_j\) và \(z_j\) không phải đệ tử trực tiếp hay gián tiếp của \(x_j\). Vẫn có thể xảy ra \(z_j\) vốn đã là cố vấn của \(x_j\).

Dữ liệu ra

In \(t_0,t_1,\ldots,t_q\), mỗi số trên một dòng.

Ràng buộc

• \(1\le n\le1\,000\,000\), \(1\le q\le30\,000\).
• \(1\le m_i\) và \(\sum_i m_i\le10^9\).
• \(1\le\hat{x}_j,\hat{z}_j\le n\).

Nếu tính sai một \(t_j\), các thay đổi kế tiếp có thể bị giải mã sai; điều này có thể dẫn tới RTE thay vì WA.

Phân nhóm

1. \(15\) điểm: \(n\le100\).
2. \(10\) điểm: \(n\le1000\).
3. \(50\) điểm: \(n\le300\,000\).
4. \(25\) điểm: không có ràng buộc thêm.

Ví dụ

7 2
0 1
1 3
1 3
2 3
2 1
5 2
5 1
3 7
2 7

2
2
3

Nguồn

CEOI 2026 - Ngày 1, bài Birdwatchers.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.