F. Трансформация директории
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У разработчика была директория $$$A$$$, в которой размещались директории и файлы. Для каждого файла посчитана его хэш сумма. В процессе работы известно, что разработчик создавал хардлинки, удалял хардлинки, создавал и удалял директории. Более формально, изменения были одного из четырех типов:

  1. mkdir /some/dir/ — создать директорию с именем /some/dir/ в директории $$$A$$$.
  2. rmdir /some/dir/ — удалить директорию с именем /some/dir/ в директории $$$A$$$.
  3. unlink /some/file — удалить хардлинку с именем /some/file в директории $$$A$$$.
  4. link /from/file /to/file — создать хардлинку с именем /to/file на /from/file в директории $$$A$$$. Тогда хэш сумма файла /to/file будет совпадать с хэш суммой файла /from/file.

При каждом изменении разработчик соблюдал правила:

  1. Нельзя создавать новые файлы, только хардлинки.
  2. Нельзя изменять файлы и директории вне директории $$$A$$$.
  3. Новые хардлинки можно создавать только на существующие в $$$A$$$ файлы.
  4. Можно удалять только пустые директории.
  5. Нельзя создавать хардлинку в директории, которой не существует.
  6. Нельзя создавать поддиректорию в директории, которой не существует.

В результате своей работы разработчик пришел к выводу, что это уже не директория $$$A$$$, а директория $$$B$$$. Тогда он решил рассмотреть все свои изменения от изначального состояния директории $$$A$$$ (далее просто "от $$$A$$$") до нынешнего состояния (далее "до $$$B$$$"). Но, к сожалению, он не смог найти историю изменений. Зато он смог найти список файлов с их хэш суммами и поддиректорий директории $$$A$$$ и список файлов с их хэш суммами и поддиректорий директории $$$B$$$.

Разработчик заметил, что пространства имен директорий в $$$A$$$ и файлов в $$$B$$$ не пересекаются, то есть нет файла в $$$B$$$ с именем, совпадающим с именем какой-либо директории в $$$A$$$. Аналогично, пространства имен файлов в $$$A$$$ и директорий в $$$B$$$ тоже не пересекаются, то есть нет файла в $$$A$$$ с именем, совпадающим с именем какой-либо директории в $$$B$$$. К тому же, если в $$$A$$$ и в $$$B$$$ есть файлы с одинаковым именем, то их хэш суммы тоже одинаковые.

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

Найдите минимальную последовательность изменений, соответствующих описанным правилам, которая преобразует директорию $$$A$$$ в директорию $$$B$$$.

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

В первой строке через пробел заданы 2 целых числа $$$n$$$ и $$$m$$$ ($$$0 \le n, m \le 10^4$$$) — количество файлов и директорий в $$$A$$$ и количество файлов и директорий в $$$B$$$ соответственно.

Каждая из следующих $$$n$$$ строк содержит имя директории (оканчивается на '/') или имя файла (не заканчивается на '/') в $$$A$$$. Имя состоит из букв английского алфавита, цифр, знаков '.' и '/' и не содержит двух подряд идущих знаков '/'. Если это имя файла, то следом за ним через пробел указана хэш сумма — строка, состоящая из строчных букв английского алфавита и цифр.

Каждая из следующих $$$m$$$ строк содержит имя директории (оканчивается на '/') или имя файла (не заканчивается на '/') в $$$B$$$. Имя состоит из букв английского алфавита, цифр, знаков '.' и '/' и не содержит двух подряд идущих знаков '/'. Если это имя файла, то следом за ним через пробел указана хэш сумма — строка, состоящая из строчных букв английского алфавита и цифр.

Длины имен от 2 до 256, длины хэш сумм от 1 до 256.

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

В первой строке выведите целое число $$$k$$$ — минимальное количество операций, за которое можно получить директорию $$$B$$$ из директории $$$A$$$. В следующих $$$k$$$ строках выведите сами операции в формате, описанном в условии.

Пример
Входные данные
4 3
/a/
/a/b.txt hash1
/a/d.txt hash2
/f/
/a/
/a/e/
/a/e/c.txt hash1
Выходные данные
5
mkdir /a/e/
rmdir /f/
unlink /a/d.txt
link /a/b.txt /a/e/c.txt
unlink /a/b.txt