Республиканская олимпиада по информатике 2019 года за 11 класс | Казахстанские олимпиады

Задача E. НурлашКО

АланашКО и НурлашКО играют с графом, и им нужна Ваша помощь. Игра начинается с ориентированного ациклического графа $G$, состоящий из $n$ вершин, без ребер, во время игры игроки выполняют $q$ операций. Операции бывают следующих типов:

Формат входного файла

Первая строка входных данных содержит три целых числа $n$, $q$ и $t$ $(1 <= n, q <= 10^6, 0 <= t <= 1)$ — количество вершин, количество операций и константное число. Каждая из следующих $q$ строк содержит описание одного запроса.

Формат выходного файла

Для каждого запроса второго типа выведите ответ в отдельной строке.

Примеры

Вход

5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3

Выход

1
0
2
0
4

Вход

5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3

Выход

1
0
2
0
4