Con trai bạn, JOI, thích nuôi thú cưng. Trong vườn nhà có \(N\) căn chuồng, được đánh số từ \(1\) đến \(N\), mỗi chuồng chứa tối đa một con vật. Có \(N-1\) lối đi hai chiều nối các chuồng, và từ một chuồng bất kỳ đều có thể đi đến mọi chuồng khác bằng các lối đi này.

JOI muốn nuôi cả mèo và chó, nhưng lo rằng chúng sẽ đánh nhau. Với mỗi trạng thái của khu vườn, trong đó mỗi chuồng có một con mèo, một con chó hoặc không có con vật nào, JOI định nghĩa mức độ nguy hiểm là số lối đi ít nhất cần chặn sao cho không có con mèo nào có thể gặp bất kỳ con chó nào bằng cách di chuyển theo các lối đi chưa bị chặn.

Ban đầu, tất cả các chuồng đều trống. JOI lập kế hoạch sử dụng khu vườn trong \(Q\) ngày. Kế hoạch của mỗi ngày là một trong ba việc:

• Đưa một con mèo mới vào chuồng \(v\) đang trống.
• Đưa một con chó mới vào chuồng \(v\) đang trống.
• Cho người hàng xóm con vật đang ở chuồng \(v\), khiến chuồng đó trở thành trống.

Là cha hoặc mẹ của JOI, bạn cần kiểm tra mức độ nguy hiểm của kế hoạch. Hãy tìm mức độ nguy hiểm của khu vườn sau khi thực hiện kế hoạch của từng ngày.

Cài đặt

Với C++, khai báo #include "catdog.h" và cài đặt bốn hàm sau:

void initialize(int N, std::vector<int> A, std::vector<int> B);
int cat(int v);
int dog(int v);
int neighbor(int v);

Đầu tiên, trình chấm gọi initialize(N, A, B) để cung cấp thông tin khu vườn. N là số chuồng. A và B là hai mảng độ dài \(N-1\); với mỗi \(0 \le i \le N-2\), có một lối đi giữa chuồng A[i] và chuồng B[i]. Đảm bảo có thể đi giữa hai chuồng bất kỳ bằng các lối đi.

Sau đó, lần lượt theo thứ tự thời gian của \(Q\) ngày, trình chấm gọi một trong các hàm:

• cat(v): đưa một con mèo mới vào chuồng \(v\) đang trống.
• dog(v): đưa một con chó mới vào chuồng \(v\) đang trống.
• neighbor(v): con vật đang ở chuồng \(v\) rời đi.

Mỗi hàm trong ba hàm này phải trả về mức độ nguy hiểm sau thay đổi của ngày tương ứng. Các thay đổi do những lần gọi hàm gây ra được giữ lại cho các ngày sau. Việc tính số lối đi cần chặn không làm thay đổi các lối đi của khu vườn.

Trên LQDOJ, nộp đúng một tệp C++ cài đặt các hàm theo chữ ký trên. Có thể cài đặt thêm các hàm phụ. Chương trình không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc tương tác với bất kỳ tệp nào khác; được phép ghi ra luồng lỗi chuẩn. Gói đính kèm chính thức vẫn được giữ để tham khảo, nhưng trình chấm của bài này chỉ hỗ trợ C++. Thông báo kỳ thi gốc quy định tối đa \(50\) lần nộp cho mỗi bài.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau; chương trình của bạn nhận dữ liệu qua các lần gọi hàm:

• Dòng đầu chứa \(N\).
• Dòng thứ \(2+i\) chứa \(A_i,B_i\), với \(0 \le i \le N-2\).
• Dòng thứ \(N+1\) chứa \(Q\).
• Dòng thứ \(N+2+j\) chứa \(T_j,v_j\), với \(0 \le j \le Q-1\).

Ở ngày thứ \(j+1\), trình chấm gọi cat(v_j) nếu \(T_j=1\), dog(v_j) nếu \(T_j=2\), hoặc neighbor(v_j) nếu \(T_j=3\).

Dữ liệu ra

Gọi \(D_j\) là giá trị trả về của hàm được gọi ở ngày thứ \(j+1\). Trình chấm mẫu in \(D_j\) trên dòng thứ \(1+j\), với \(0 \le j \le Q-1\).

Ràng buộc

• \(1 \le N \le 100000\); \(1 \le Q \le 100000\).
• Các chuồng được đánh số từ \(1\) đến \(N\); có \(N-1\) lối đi hai chiều và có thể đi giữa hai chuồng bất kỳ.
• Mỗi chuồng có tối đa một con vật. Mỗi thao tác thêm con vật được thực hiện trên một chuồng trống; mỗi thao tác cho con vật đi được thực hiện trên một chuồng đang có con vật.
• Giới hạn thời gian: \(3\) giây. Giới hạn bộ nhớ: \(512\) MB.

Phân nhóm

1. \(8\) điểm: Giới hạn \(N\): \(1 \le N \le 15\); Giới hạn \(Q\): \(1 \le Q \le 100\)
2. \(30\) điểm: Giới hạn \(N\): \(1 \le N \le 1000\); Giới hạn \(Q\): \(1 \le Q \le 1000\)
3. \(62\) điểm: Giới hạn \(N\): \(1 \le N \le 100000\); Giới hạn \(Q\): \(1 \le Q \le 100000\)

Ví dụ giao tiếp

Có \(5\) chuồng và \(4\) lối đi: giữa chuồng \(1\) và \(2\), giữa chuồng \(2\) và \(3\), giữa chuồng \(2\) và \(4\), giữa chuồng \(4\) và \(5\).

Ban đầu, giả sử JOI đã đưa một con mèo vào chuồng \(3\) và một con chó vào chuồng \(5\). Chặn lối đi giữa chuồng \(2\) và \(4\) sẽ ngăn mèo và chó gặp nhau. Mức độ nguy hiểm lúc này là \(1\).

Tiếp theo, giả sử JOI đưa thêm một con mèo vào chuồng \(2\) và một con chó vào chuồng \(1\). Chặn lối đi giữa chuồng \(2\) và \(4\), cùng với lối đi giữa chuồng \(1\) và \(2\), sẽ ngăn mèo và chó gặp nhau. Mức độ nguy hiểm lúc này là \(2\).

Cuối cùng, giả sử JOI cho người hàng xóm con mèo ở chuồng \(2\). Lúc này chỉ cần chặn lối đi giữa chuồng \(2\) và \(3\), nên mức độ nguy hiểm là \(1\).

Nguồn

JOI Open 2018 - Cats or Dogs, đề tiếng Anh, thông báo cài đặt và gói mã mẫu chính thức. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.