Công ty JOI có tổng cộng \(N\) máy chủ trên khắp thế giới. Ban đầu, mỗi máy chủ chứa một mẩu thông tin quan trọng, và các mẩu thông tin ban đầu của các máy chủ đôi một khác nhau. Công ty đang xây dựng các đường truyền số giữa các máy chủ để chia sẻ thông tin. Khi có một đường truyền nối hai máy chủ, chúng có thể trao đổi thông tin với nhau. Thông tin cũng có thể được trao đổi giữa hai máy chủ nếu có thể đi từ máy chủ này đến máy chủ kia qua các đường truyền đang hoạt động.

Mỗi máy chủ có một hệ thống đồng bộ hóa hiệu năng cao. Khi hai máy chủ có thể trao đổi thông tin và tập thông tin của chúng khác nhau, chúng tự động đồng bộ hóa. Sau khi máy chủ \(A\) và máy chủ \(B\) đồng bộ hóa, cả hai đều chứa tất cả các mẩu thông tin đã có ở ít nhất một trong hai máy chủ trước khi đồng bộ hóa.

Để giảm chi phí, chỉ có \(N-1\) đường truyền được dự kiến xây dựng. Nếu cả \(N-1\) đường truyền đều hoạt động, giữa hai máy chủ bất kỳ sẽ có đúng một đường đi không đi qua cùng một máy chủ quá một lần.

Ban đầu, tại thời điểm \(0\), chưa có đường truyền nào được xây dựng. Một số đường truyền được xây dựng trong điều kiện khắc nghiệt, chẳng hạn trong sa mạc hoặc dưới đáy biển, nên có thể ngừng hoạt động. Khi một đường truyền ngừng hoạt động, nó không thể được sử dụng cho đến khi được xây dựng lại.

Tại mỗi thời điểm \(j\) với \(1 \le j \le M\), trạng thái của đúng một đường truyền thay đổi. Nếu đường truyền đó không hoạt động ngay trước thời điểm \(j\), nó được xây dựng tại thời điểm \(j\); nếu đang hoạt động, nó ngừng hoạt động tại thời điểm \(j\). Mọi quá trình đồng bộ hóa sau lần thay đổi này đều hoàn tất trước thời điểm \(j+1\). Thông tin đã nhận được vẫn được máy chủ lưu giữ khi đường truyền ngừng hoạt động.

Yêu cầu

Cho các đường truyền dự kiến xây dựng và danh sách các lần thay đổi trạng thái, hãy xác định số mẩu thông tin khác nhau được lưu tại từng máy chủ trong số \(Q\) máy chủ được hỏi ở thời điểm \(M+1\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(N, M, Q\) cách nhau bởi dấu cách: số máy chủ, số lần thay đổi trạng thái đường truyền và số máy chủ được hỏi.
• \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(X_i, Y_i\) cách nhau bởi dấu cách. Đường truyền thứ \(i\), khi hoạt động, nối máy chủ \(X_i\) với máy chủ \(Y_i\).
• \(M\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(D_j\), cho biết đường truyền \(D_j\) thay đổi trạng thái tại thời điểm \(j\).
• \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa số nguyên \(C_k\), là máy chủ cần xác định số mẩu thông tin khác nhau vào cuối quá trình.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(k\) chứa một số nguyên là số mẩu thông tin khác nhau được lưu tại máy chủ \(C_k\) ở thời điểm \(M+1\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le M \le 200\,000\).
• \(1 \le Q \le N\).
• \(1 \le X_i, Y_i \le N\) và \(X_i \ne Y_i\) với \(1 \le i \le N-1\).
• \(1 \le D_j \le N-1\) với \(1 \le j \le M\).
• \(1 \le C_k \le N\) với \(1 \le k \le Q\).
• Các giá trị \(C_k\) đôi một khác nhau.
• Nếu tất cả các đường truyền đều hoạt động, có thể đi từ một máy chủ bất kỳ đến mọi máy chủ khác qua các đường truyền.

Chấm điểm

• Subtask 1 (\(30\) điểm): \(Q = 1\).
• Subtask 2 (\(30\) điểm): \(X_i = i\) và \(Y_i = i+1\) với mọi \(1 \le i \le N-1\).
• Subtask 3 (\(40\) điểm): Không có ràng buộc bổ sung.

5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5

3
5
4

Giả sử ban đầu máy chủ \(i\) chứa mẩu thông tin \(i\) với \(1 \le i \le 5\).

• Tại thời điểm \(1\), đường truyền \(1\) được xây dựng, nối máy chủ \(1\) và \(2\). Sau khi đồng bộ hóa, cả hai máy chủ đều chứa các mẩu thông tin \(1, 2\).
• Tại thời điểm \(2\), đường truyền \(2\) được xây dựng, nối máy chủ \(1\) và \(3\). Cùng với đường truyền \(1\), ba máy chủ \(1, 2, 3\) được kết nối với nhau và đều chứa các mẩu thông tin \(1, 2, 3\).
• Tại thời điểm \(3\), đường truyền \(1\) ngừng hoạt động vì nó đang hoạt động ngay trước thời điểm này.
• Tại thời điểm \(4\), đường truyền \(4\) được xây dựng, nối máy chủ \(2\) và \(5\). Cả hai máy chủ đều chứa các mẩu thông tin \(1, 2, 3, 5\). Máy chủ \(1\) và \(2\) không thể trao đổi thông tin vì đường truyền \(1\) đã ngừng hoạt động.
• Tại thời điểm \(5\), đường truyền \(4\) ngừng hoạt động.
• Tại thời điểm \(6\), đường truyền \(3\) được xây dựng, nối máy chủ \(2\) và \(4\). Cả hai máy chủ đều chứa các mẩu thông tin \(1, 2, 3, 4, 5\).

Vì vậy, vào cuối quá trình, các máy chủ \(1, 4, 5\) lần lượt chứa \(3, 5, 4\) mẩu thông tin khác nhau.