Имеется N коробок, каждая выкрашена в свой отдельный цвет. В эти коробки положено M шаров, тех же N цветов. Расположение шаров по коробкам известно. Требуется разложить шары по коробкам так, чтобы в каждой коробке оказались только шары ее цвета и для перекладывания потребовалось минимальное число действий. Одним действием считается обмен двух шаров местами или перекладывание одного шара из коробки в коробку.

Во входном файле записаны числа N и M (2 ≤ N ≤ 10, 1 ≤ M ≤ 100). Далее следуют M пар чисел, задающих цвет очереднего шара и номер коробки, в которой он находится.

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

input.txt	output.txt
4 8 1 3 2 4 3 2 4 1 2 4 1 1 2 4 3 4	6 1 4 4 3 1 3 3 1 2 3 3 4 2 2 4 2 2 4 2 2