Vấn đề này được trình bày theo các bài trong kì thi OLP tin học sinh viên, giới hạn (subtask) được xếp ở cuối.

Việc thiết kế mô hình mạng có tác động đáng kể đến nền kinh tế của một quốc gia. Công ty \(SNC\) (Secure Network Communication) phát minh ra cách kết nối mạng trong thành phố như sau: Thành phố được chia thành \(n\) vùng được gán một mã số trong khoảng từ \(1\) tới \(n\). \(n - 1\) kết nối giữa các vùng tạo thành một đồ thị cây với vùng mạng gốc mang mã số \(1\), từ đó định nghĩa vùng mạng cha và các vùng mạng con. Mỗi vùng mạng có một máy chủ duy nhất. Mô hình của công ty có ưu điểm là xác định đường đi giữa hai vùng rất nhanh chóng và đơn giản, do trong đồ thị cây giữa hai đỉnh chỉ có duy nhất một đường đi.

Để đảm bảo các mạng con được cấu hình đúng và có đường truyền ổn định, sau khi lắp đặt xong mạng trong thành phố \(W\) theo mô hình trên, công ty bắt đầu tiến hành quá trình kiểm thử. Mỗi máy chủ của một vùng sẽ lưu một bit (gọi là bit tĩnh, ban đầu bằng \(0\)). Các bit tĩnh được cập nhật theo hai lệnh truyền multicast như sau:

• \(UPCAST\:i\): lật bit tĩnh trong máy chủ của các vùng trên đường mạng từ vùng gốc tới vùng mạng mã \(i\), bao gồm cả bit tĩnh trong máy chủ của vùng gốc và máy chủ của vùng \(i\).
• \(DOWNCAST\:i\): lật bit tĩnh trong máy chủ của các vùng mạng con bắt đầu từ vùng mạng \(i\).

Ví dụ với sơ đồ kết nối như hình dưới đây thì lệnh \(UPCAST\:6\) là lệnh lật bit tĩnh trong máy chủ của các vùng \(1, 2, 5, 6\), \(DOWNCAST\:2\) là lệnh lật bit tĩnh trong máy chủ tương ứng với các vùng \(2, 4, 5, 6\).

Yêu cầu

Sau khi thực hiện tất cả các lệnh \(UPCAST\) và \(DOWNCAST\), xác định bit tĩnh ở mỗi máy chủ trong vùng đang ở trạng thái nào.

Dữ liệu

Vào từ thiết bị nhập chuẩn với định dạng như sau:

• Dòng đầu tiên chứa hai số nguyên \(n\), số vùng mạng trong thành phố.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \le u, v \le n)\) với ý nghĩa có kết nối hai chiều giữa hai vùng mạng \(u\) và \(v\).
• Dòng thứ \(n + 1\) chứa số nguyên \(l\), số câu lệnh kiểm thử.
• \(l\) dòng cuối cùng, mỗi dòng chứa một lệnh được mô tả theo quy cách như trên.

Kết quả

Đưa ra thiết bị xuất chuẩn một xâu nhị phân duy nhất, chữ cái thứ \(i\) của xâu là trạng thái bit kiểm tra của máy chủ vùng \(i\).

Ví dụ

Dữ liệu vào:

6
1 2
1 3
2 4
2 5
5 6
2
UPCAST 6
DOWNCAST 2

Kết quả ra:

100100

Giới hạn

Subtask \(1\) \((30\%\) số điểm\()\): \(1 \le n, l \le 1000\).

Subtask \(2\) \((30\%\) số điểm\()\): \(1 \le n, l \le 2*10^5\), không có thao tác \(UPCAST\).

Subtask \(3\) \((40\%\) số điểm\()\): \(1 \le n, l \le 2*10^5\).