База даних
На підприємстві працює N співробітників. Між ними існує M зв'язків "начальник-підлеглий". У співробітника може бути кілька начальників і підлеглих. Не існує послідовності зв'язків "начальник-підлеглий", яка починається і закінчується одним і тим же співробітником.
Доступ до корпоративної бази даних регулюється системою прав. У кожний момент часу для кожного співробітника однозначно відомо, чи має він права на доступ до бази даних чи ні. На початку, коли базу даних тільки встановили на підприємстві, ніхто не мав прав на доступ до неї. У процесі роботи з базою даних права на доступ змінювалися за допомогою таких операцій:
Адміністратор надає права співробітнику X.
Адміністратор позбавляє прав співробітника X.
Співробітник Х починає ділитися правами з усіма безпосередніми підлеглими.
Співробітник Х починає ділитися правами з усіма безпосередніми підлеглими. Потім для кожного безпосереднього підлеглого співробітника Х виконується операція 4.
Співробітник Х перестає ділитися своїми правами з усіма безпосередніми підлеглими.
Співробітник X має права на доступ до корпоративної бази даних, якщо виконується хоча б одна з таких умов:
Останньою операцією Адміністратора щодо співробітника X було надання йому прав.
Хоча б один з безпосередніх керівників, який має права на даний момент, ділиться з ним правами на доступ.
Зверніть увагу. Якщо співробітник поділився правами доступу зі своїми підлеглими, а потім їх втратив, він все одно продовжує ділитися правами зі своїми підлеглими. Однак вони не зможуть цим скористатися для отримання прав, поки цей співробітник знову не отримає права на доступ. (див. другий приклад з умови).
Напишіть програму, яка за заданою послідовністю операцій зі зміни прав на доступ до корпоративної бази даних для кожного співробітника визначить, чи буде він мати права на доступ після виконання цієї послідовності операцій.
Для заданої послідовності операцій виконуються такі обмеження. Для кожного співробітника жодна з операцій 1 і 2 не зустрічається двічі поспіль. Не зустрічаються операції 3 і 4, коли у відповідний момент часу співробітник не має прав на доступ. Не зустрічається операція 5, коли у відповідний момент часу співробітник не ділиться правами зі своїми підлеглими.
Вхідні дані
Перша рядок містить два цілих числа: кількість співробітників підприємства N (1 ≤ N ≤ 10000) і кількість зв'язків "начальник-підлеглий" M (1 ≤ M ≤ 50000). Наступні M рядків містять по два натуральних числа X і Y (1 ≤ X, Y ≤ N), визначаючи, що X є безпосереднім начальником Y. Наступний рядок містить число K (1 ≤ K ≤ 20000) - кількість операцій зміни прав. Наступні K рядків містять по два натуральних числа T і X (1 ≤ T ≤ 5, 1 ≤ X ≤ N) - тип операції і номер співробітника, до якого вона відноситься, відповідно.
Вихідні дані
Єдиний рядок повинен містити N цілих чисел, розділених пробілами. i-те число дорівнює 1 або 0, в залежності від того, має i-й співробітник права на доступ після виконання заданих команд (1), чи ні (0).
Пояснення до прикладу 1
1-й співробітник отримує права на доступ від адміністратора
1-й співробітник починає ділитися правами на доступ з 2-м і 3-м співробітниками. У свою чергу, 2-й ділиться з 4-м, а 3-й ділиться з 4-м і 5-м співробітниками.
2-й співробітник отримує права на доступ від адміністратора.
1-й співробітник припиняє ділитися правами на доступ з 2-м і 3-м співробітниками. В результаті 3-й співробітник втрачає права на доступ, а 2-й співробітник - ні, оскільки він має права на доступ від адміністратора. 4-й співробітник теж не втрачає права на доступ, оскільки 2-й співробітник має права на доступ і ділиться з ним правами. 5-й співробітник втрачає права, тому що 3-й співробітник хоча і ділиться правами, на даний момент прав не має.
Пояснення до прикладу 2
1-й співробітник отримує права на доступ від адміністратора.
1-й співробітник починає ділитися правами на доступ з 2-м співробітником. 2-й співробітник отримує права, тому що 1-й має права і ділиться правами з ним.
Адміністратор позбавляє прав 1-го співробітника. 2-й співробітник також втрачає права, оскільки 1-й хоча і ділиться з ним правами, на даний момент їх не має.
1-й співробітник отримує права на доступ від адміністратора. 2-й співробітник отримує права, оскільки 1-й співробітник має права на даний момент часу і ділиться з ним правами.