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

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

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

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

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

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

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

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

Примеры

Вход

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