Задача A. Неправильный кабель

Автор:А. Кленин, А. Максимов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:45  

Условие

Принтер соединен с компьютером кабелем, содержащим N линий данных, пронумерованных от 1 до N. Принтер имеет N контактов, также пронумерованных от 1 до N. При правильном подключении номер линии данных совпадает с номером контакта принтера (см. рис. 1).

По каждой линии данных i может передаваться сигнал si — "0" либо "1". При передаче в принтер кода символа по линиям 1, 2, ..., N одновременно передаются сигналы s1, s2, ..., sN. Например, при N = 8 символу "A" может соответствовать код 01000001 — это значит, что по линиям с номерами 2 и 8 должен быть передан сигнал "1", а по остальным — сигнал "0" (см. рис. 1).

В результате неправильного монтажа кабеля линии могли быть соединены не с теми контактами принтера. Известно, что линии не соединены между собой и не оборваны. На рис. 2 изображен пример неправильного монтажа кабеля при N = 8.

Схему монтажа кабеля можно обозначить перестановкой π1π2, … , πN чисел от 1 до N, где πi - номер линии, подсоединенной к i-му контакту принтера. Например, правильному монтажу, изображенному на рис. 1, соответствует перестановка 12345678, а неправильному монтажу, изображенному на рис. 2, — перестановка 12534687.

При передаче кода s1, s2, … , sN по кабелю принтер получит код , который может отличаться от исходного из-за ошибок монтажа. Например, при передаче кода 01001101 по кабелю на рис. 2 принтер получит код 01100110. Заметим, что код 11000100 здесь будет передан правильно.

Чтобы проверить, правильно ли спаян кабель, на линии данных подали несколько раз-личных кодов, и записали соответствующие коды, полученные принтером.

Даны M пар кодов. Код состоит из N символов, каждый из которых либо "0", либо "1". Первым в паре стоит код, переданный с компьютера, вторым — код, полученный принтером. Программа должна однозначно определить схему монтажа кабеля (перестановку чисел от 1 до N), либо сообщить, что это невозможно.

Формат входного файла

Входной файл содержит в первой строке числа N M. В каждой из последующих M строк входного файла содержится по два кода, разделенных пробелом.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100, 1 ≤ M ≤ 10000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
8 3
11110000 11110000
11001100 11001010
10101010 10101001
1 2 3 4 5 8 6 7

0.143s 0.014s 19