G. Плачь, река
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан ориентированный ациклический граф с $$$n$$$ вершинами и $$$m$$$ рёбрами. Каждая вершина изначально окрашена в синий цвет.

Определим игру в графе следующим образом:

  • Изначально фишка помещается на вершину $$$s$$$.
  • Cry и River по очереди перемещают фишку на вершину, в которую существует направленное ребро из текущей позиции, при этом Cry ходит первым.
  • Cry выигрывает, если фишка когда-либо достигнет вершины без исходящих рёбер после хода любого из игроков.
  • River выигрывает, если фишка достигает красной вершины после хода любого из игроков.
  • Если игроки достигают вершины, которая одновременно красная и не имеет исходящих рёбер, выигрывает River.

Поскольку граф ацикличен, можно показать, что игра всегда заканчивается за конечное число ходов.

Обратите внимание, что Cry и River могут выиграть игру немедленно, если начальная вершина $$$s$$$ не имеет исходящих рёбер или является красной соответственно.

Вам необходимо обработать $$$q$$$ запросов следующего вида:

  • 1 u: обновить цвет вершины $$$u$$$ на красный. Гарантируется, что вершина $$$u$$$ была синей до этого обновления.
  • 2 u: Если игра в графе играется с фишкой, изначально находящейся на вершине $$$u$$$, и оба игрока играют оптимально, выигрывает ли Cry?
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$ ,$$$1 \leq m,q \leq 2\cdot 10^5$$$).

Следующие $$$m$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u,v \leq n$$$), что означает, что существует ребро от $$$u$$$ к $$$v$$$.

Следующие $$$q$$$ строк содержат по два целых числа $$$x$$$ и $$$u$$$ ($$$1 \leq x \leq 2, 1 \leq u \leq n$$$) – обозначающие тип запроса и вершину, на которой выполняется запрос.

Гарантируется, что данный граф является ориентированным ациклическим графом. Кроме того, ни одно ребро не указано более одного раза.

Гарантируется, что сумма $$$n$$$, сумма $$$m$$$ и сумма $$$q$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого запроса второго типа выведите YES, если выигрывает Cry. В противном случае выведите NO. Каждая буква может быть выведена в верхнем или нижнем регистре.

Пример
Входные данные
1
7 8 10
1 2
1 3
1 4
2 5
3 6
5 7
2 3
3 4
2 1
1 3
1 4
2 1
2 2
2 3
2 4
2 5
2 6
2 7
Выходные данные
YES
NO
YES
NO
NO
YES
YES
YES
Примечание

Ниже показан граф из примера.

Изначально все вершины синие. Таким образом, Cry не может проиграть, и в конечном итоге фишка будет перемещена на вершину без исходящих рёбер.

После того как вершины $$$3$$$ и $$$4$$$ будут окрашены в красный, вершины $$$1,3,4$$$ теперь начинают как выигрышные для River при оптимальной игре. Если игра начинается на вершинах $$$3$$$ и $$$4$$$, River выигрывает немедленно. Если игра начинается на вершине $$$1$$$, один из возможных ходов игры может быть следующим:

  • Cry перемещает фишку на вершину$$$2$$$.
  • River перемещает фишку на вершину $$$3$$$, которая красная, поэтому выигрывает River.
.

Можно показать, что Cry все равно выигрывает при оптимальной игре для всех остальных вершин.