考虑与行和列的表。列编号从1到C为简便起见，在表中的项目是由小写字母串。

您被授予这样的表操作排序（K）：排序（k）在（而列的顺序不会改变）在k列的值的顺序排序表中的行。排序是稳定的，即，具有相同的值在k列的行，则保持原来的顺序。例如，应用排序（2），以表1产率表2。

我们感兴趣的是这样的排序操作的顺序。这些操作被依次施加到相同的表。例如，在施加顺序排序（2） 排序（1）表1产率表3中。

排序操作的两个序列被称为等价的，如果，对任何的表，它们具有相同的效果。例如，排序（2） 排序（2） 排序（1）等同于排序（2） 排序（1）。然而，它不等于排序（1） 排序（2）中，因为在表1中的效果是不同的。

任务

定的排序操作的序列，确定的最短等效序列。-Consider a table with rows and columns. The columns are numbered　1 to C. For simplicity s sake, the items in the table are strings consisting of lower case letters.

You are given the operation Sort(k) on such tables: Sort(k) sorts the rows of a table in the order of the values in column k (while the order of the columns does not change). The sort is stable, that is, rows that have equal values in column k, remain in their original order. For example, applying Sort(2) to Table 1 yields Table 2.

We are interested in sequences of such sort operations. These operations are successively applied to the same table. For example, applying the sequence Sort(2)　Sort(1) to Table 1 yields Table 3.

Two sequences of sort operations are called equivalent if, for any table, they have the same effect. For example, Sort(2)　Sort(2)　Sort(1) is equivalent to Sort(2)　Sort(1). However, it is not equivalent to Sort(1)　Sort(2), because the effect on Table 1 is different.

Task

Given a sequence of sort