Database#3037
In a company, there are employees, and among them, there are "supervisor-subordinate" relationships. An employee can have multiple supervisors and subordinates, but there is no cycle of "supervisor-subordinate" connections that starts and ends with the same employee.
Access to the corporate database is controlled by a system of rights. At any moment, it is known whether each employee has access rights to the database. Initially, when the database was set up, no one had access rights. Over time, access rights are modified through the following operations:
The administrator grants access rights to employee .
The administrator revokes access rights from employee .
Employee begins sharing access rights with all direct subordinates.
Employee begins sharing access rights with all direct subordinates. Then, for each direct subordinate of employee , operation is performed.
Employee stops sharing access rights with all direct subordinates.
Employee has access rights to the corporate database if at least one of the following conditions is satisfied:
The last operation by the administrator concerning employee was granting them rights.
At least one of the direct supervisors, who currently has rights, shares access rights with them.
Note: If an employee shares access rights with their subordinates and then loses their own rights, they continue to share rights with their subordinates. However, the subordinates cannot gain rights from this until the employee regains access rights. (Refer to the second example in the explanation).
Write a program that, given a sequence of operations modifying access rights to the corporate database, determines for each employee whether they will have access rights after executing this sequence of operations.
For the given sequence of operations, the following constraints apply. For each employee, operations and do not appear consecutively. Operations and do not occur when the employee does not have access rights at that time. Operation does not occur when the employee is not sharing rights with their subordinates.
The first line contains two integers: the number of employees (1 \le N \le 10000) and the number of "supervisor-subordinate" connections (1 \le M \le 50000). The next lines each contain two natural numbers and (1 \le X, Y \le N), indicating that is the direct supervisor of . The following line contains the number (1 \le K \le 20000) — the number of operations modifying rights. The subsequent lines each contain two natural numbers and (1 \le T \le 5, 1 \le X \le N) — the type of operation and the employee number it applies to, respectively.
The output should be a single line containing integers, separated by spaces. The -th number is if the -th employee has access rights after executing the given commands, or if they do not.
Explanation for Example 1
The st employee receives access rights from the administrator.
The st employee starts sharing access rights with the nd and rd employees. Consequently, the nd shares with the th, and the rd shares with the th and th employees.
The nd employee receives access rights from the administrator.
The st employee stops sharing access rights with the nd and rd employees. As a result, the rd employee loses access rights, but the nd employee does not, as they have access rights from the administrator. The th employee also retains access rights because the nd employee has rights and shares them. The th employee loses rights because the rd employee, although sharing rights, does not currently have them.
Explanation for Example 2
The st employee receives access rights from the administrator.
The st employee starts sharing access rights with the nd employee. The nd employee receives rights because the st has rights and shares them.
The administrator revokes rights from the st employee. The nd employee also loses rights because the st, although sharing rights, does not currently have them.
The st employee receives access rights from the administrator. The nd employee receives rights because the st employee currently has rights and shares them.
Example 1