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

В этой задаче вам предстоит реализовать алгоритм дефрагментации жесткого диска. Жесткий диск состоит из последовательности кластеров, пронумерованных целыми числами от 1 до n. На диске записано m файлов, i-й файл занимает кластеры с номерами ai, 1, ai, 2, ..., ai, ni. Эти кластеры не обязательно расположены последовательно на диске, однако порядок их задания соответствует их последовательности в файле (в кластере ai, 1 содержится первый фрагмент i-го файла, в кластере ai, 2 — второй фрагмент и т.д.). Также на диске обязательно имеется один или несколько свободных кластеров, не занятых файлами.

Разрешается выполнять операции копирования содержимого кластера с номером i в кластер с номером j (i и j должны быть различны). При этом если в кластере с номером j хранилась какая-то информация, она утрачивается безвозвратно. Кластеры не очищаются, просто после завершения дефрагментации некоторые из них объявляются неиспользуемыми (хотя, возможно, продолжают содержать некоторые фрагменты файлов).

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

Выведите последовательность операций, приводящих к дефрагментации диска. Обратите внимание, что не требуется минимизировать количество операций, однако оно не должно превосходить 2n.

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

В первой строке содержатся два целых числа n и m (1 ≤ n, m ≤ 200) — количество кластеров и количество файлов, соответственно. Следующие m строк содержат описания файлов. Первое число в строке — ni (ni ≥ 1), количество кластеров, которые занимает i-й файл. Далее следуют ni чисел ai, 1, ai, 2, ..., ai, ni (1 ≤ ai, j ≤ n). Гарантируется, что каждый номер кластера встречается не более одного раза и , т.е. существует хотя бы один неиспользуемый кластер. Числа в каждой строке разделены пробелами.

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

В первой строке выведите одно целое число k (0 ≤ k ≤ 2n) — количество операций, требующихся для дефрагментации диска. Следующие k строк должны содержать описания операций в формате «i j» (скопировать содержимое кластера с номером i в кластер с номером j).

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

Пусть диск состоит из 8 кластеров и на нем расположены два файла. Первый файл занимает два кластера, второй — три кластера. Рассмотрим примеры корректного и некорректного расположения файлов после дефрагментации.

Пример 2: каждый файл должен занимать непрерывную область памяти.

Пример 3: порядок файлов между собой не важен, сначала может быть записан второй файл, потом — первый.

Пример 4: нарушать порядок фрагментов файла между собой не разрешается.

Пример 5: неиспользуемые кластеры должны располагаться в конце, а в данном примере неиспользуемые кластеры — 3, 7, 8.