Quốc gia A được biểu diễn là một cây vô hướng với ~n~ thành phố được nối bởi ~n-1~ đường đi. Chính phủ đang thiết kế hệ thống cơ sở dữ liệu để đánh dấu các vùng xanh để chuẩn bị cho các trường hợp có thiên tai, dịch bệnh xảy ra.

Ta sẽ gọi máy tính lưu toàn bộ cơ sở dữ liệu là máy chủ, các máy của người dân là máy trạm.

Khi thiên tai xảy ra, chính phủ sẽ đánh dấu các vùng xanh, bao gồm một số nguyên dương các thành phố liên thông với nhau (tức, hai thành phố trong vùng xanh luôn đi được tới nhau mà không cần đi ra khỏi vùng xanh).

Máy chủ và các máy trạm đều biết thông tin của cây, tuy nhiên chỉ có máy chủ mới biết thông tin của các vùng xanh và sẽ có một số thời điểm các vùng xanh được cập nhật.

Một quá trình tương tác giữa máy trạm và máy chủ diễn ra như sau:

1. Khi người dân cần biết thông tin về một số vùng xanh, họ sẽ liệt kê ra một danh sách gồm thành phố họ đang sống và một số thành phố có đường đi trực tiếp với thành phố đó, ta gọi danh sách này là ~P~ (với ~P_0~ là thành phố của họ). Họ cần biết trong ~P~ có tồn tại thành phố thuộc vùng xanh hay không

2. Họ sẽ gửi một xâu nhị phân rồi gửi cho máy chủ, ta gọi là xâu ~S~.

3. Máy chủ nhận xâu nhị phân ~S~, gửi về máy trạm xâu nhị phân ~T~.

4. Máy trạm nhận xâu nhị phân ~T~ và cho biết một thành phố trong danh sách ~P~ thuộc vùng xanh hoặc thông báo không có thành phố nào trong danh sách ~P~ thuộc vùng xanh.

Hãy thiết kế máy chủ và máy trạm sao cho tổng lượng thông tin cần gửi là ít nhất (xem chi tiết ở phần subtask và scoring).

Implementation

Client

Bạn cần cài đặt:

namespace client

Trong client, bạn cần cài đặt các hàm sau:

void init(vector <int> par)

• Mảng ~par~ có độ dài cho ~n - 1~, biểu diễn các cạnh trong đồ thị, trong đó, với mỗi ~i~ thì có cạnh nối giữa ~i + 1~ và ~par_i~ trên cây (~0 \le i < n - 1~, ~par_i\le i~).

string request(vector <int> P)

• Mảng ~P~ sẽ là danh sách mà người dân muốn kiểm tra, trong đó, ~P_0~ sẽ là thành phố người đó đang sống và có đường đi trực tiếp đến ~P_i~ (~i > 0~). Hàm trả về xâu nhị phân ~S~, xâu này sẽ được gửi cho máy chủ.

int answer(string T)

• Xâu ~T~ là xâu được gửi về từ máy chủ sau khi thực hiện lệnh request. Bạn cần trả về một thành phố trong danh sách ~P~ thuộc vùng xanh hoặc trả về ~-1~ nếu không tồn tại.

Server

Bạn cần cài đặt:

namespace server

Trong server, bạn cần cài đặt các hàm sau:

void init(vector<int> par)

• Mảng ~par~ có độ dài cho ~n - 1~, biểu diễn các cạnh trong đồ thị, trong đó, với mỗi ~i~ thì có cạnh nối giữa ~i + 1~ và ~par_i~ trên cây (~0 \le i < n - 1~, ~par_i\le i~).

void update(vector<int> green)

• Mảng green chứa thông tin các thành phố thuộc vùng xanh.
• Lưu ý: Sau truy vấn này, chỉ có các thành phố này thuộc vùng xanh, các thành phố không trong danh sách này sẽ nằm ngoài vùng xanh.

string query(string S)

• Xâu nhị phân ~S~ được gửi từ máy trạm, hàm cần trả về một xâu nhị phân ~T~.

Note

• Được phép khai báo thêm biến và hàm toàn cục trong hai namespace hoặc ngoài hai namespace, nhưng không được đặt tên hàm là main.
• Các hàm trong cùng một namespace sẽ dùng chung dữ liệu, các biến toàn cục nằm ngoài hai namespace sẽ bị reset khi truyền thông tin giữa hai hàm.

Subtask

Trong mọi subtask: ~5 \le n \le 65536~.

Trong mỗi test, hàm 'update' và 'request' sẽ được gọi tối đa ~1000~ lần.

Scoring

• Gọi ~d = |S| + |T|~ trong mỗi lần request và query.
• ~D = max(d)~ trong mọi lần request và query.
• ~D_{max} = max(D)~ trong mọi test của một subtask và ~T~ là điểm của subtask đó, điểm của bạn cho subtask đó được tính như sau: