G. Безопасная работа с памятью
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как язык Rust гарантирует безопасную работу с памятью? Для этого вводятся такие концепции, как владение, заимствование и время жизни. Вадим, к сожалению, не смог разобраться, как установить компилятор Rust, поэтому решил потренироваться на упрощенной версии языка.

В языке, который использует Вадим, существует четыре операции:

  • 1 $$$a$$$ — создать переменную с названием $$$a$$$.
  • 2 $$$b$$$ $$$a$$$ — создать Read-only ссылку с названием $$$b$$$ на переменную с названием $$$a$$$.
  • 3 $$$b$$$ $$$a$$$ — создать Writable ссылку с названием $$$b$$$ на переменную с названием $$$a$$$.
  • 4 $$$a$$$ — удалить переменную либо ссылку с названием $$$a$$$.

Вадим предоставил вам последовательность операций, которая представляет некоторую программу, реализованную на этом языке. Вам нужно проверить, что программа безопасно работает с памятью; для этого после каждой операции в программе должны выполняться следующие правила:

  1. На каждую переменную может ссылаться только один вид ссылок, но не два одновременно:
    • одна или более Read-only ссылок;
    • ровно одна Writable ссылка.
  2. Каждая ссылка ссылается на существующую переменную (неудаленную).
Входные данные

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

В первой строке каждого набора входных данных содержится единственное целое число $$$n$$$ — количество операций в программе Вадима.

В следующих $$$n$$$ строках заданы операции в одном из следующих форматов:

  • 1 $$$a$$$ — создать переменную с названием $$$a$$$ ($$$1 \le |a| \le 10$$$).
  • 2 $$$b$$$ $$$a$$$ — создать Read-only ссылку с названием $$$b$$$ на переменную с названием $$$a$$$ ($$$1 \le |a|, |b| \le 10$$$).
  • 3 $$$b$$$ $$$a$$$ — создать Writable ссылку с названием $$$b$$$ на переменную с названием $$$a$$$ ($$$1 \le |a|, |b| \le 10$$$).
  • 4 $$$a$$$ — удалить переменную либо ссылку с названием $$$a$$$ ($$$1 \le |a| \le 10$$$).

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

Также предоставляются следующие гарантии:

  • При создании переменной либо ссылки используется новое, уникальное название, состоящее только из строчных букв латинского алфавита.
  • Ссылка может ссылаться только на переменную.
  • В момент создания любой ссылки переменная, на которую ссылается эта ссылка, уже существует (была создана и еще не удалена).
  • Каждая переменная либо ссылка удаляется не более одного раза и только после ее создания.
Выходные данные

Для каждого набора входных данных выведите «Yes» (без кавычек), если программа Вадима безопасно работает с памятью, в противном случае выведите «No» (без кавычек).

Пример
Входные данные
6
3
1 a
2 b a
3 c a
3
1 a
2 b a
2 c a
3
1 a
2 b a
4 a
4
1 a
2 b a
4 b
4 a
4
1 a
2 b a
4 b
3 c a
1
1 a
Выходные данные
No
Yes
No
Yes
Yes
Yes
Примечание

В первом наборе входных данных после третьей команды нарушается правило №$$$1$$$.

Во втором наборе входных данных после каждой команды на переменной $$$a$$$ существуют только Read-only ссылки.

В третьем наборе входных данных после третьей команды нарушается правило №$$$2$$$.

В пятом наборе входных данных Writable ссылка создается после удаления Read-only ссылки, поэтому правило №$$$1$$$ не нарушается.