09. March

Март на дворе - а у нас ни одной задачи про котиков, про кошечек и про их любовь...

Вот логическая задачка. Коты Вася, Барсик и Мурзик любят кошек Мурку, Багиру и Веснушку. Они образуют три влюблённые пары, причём ни в одной имена не начинаются на одну букву. Кто кого любит, если вчера Мурзик подрался с кэт-френдом Веснушки из-за шкурки от сардельки? Вы, конечно, без труда её решите. А вот компу такое не решить: он только с формализованными задачами справляется.

Чтобы компьютеру было легче, обозначим котов и кошек трёхзначными числами: первая цифра - пол (1 - кот, 2 - кошка, а далее 00, 01 и т.д.), а утверждения об их взаимоотношениях будем вводить в таком формате: в строке два имени, а между ними "+" (любит) или "-" (не любит). Разработайте программу, которая по данным о количестве котов и кошек (их поровну) и о взаимоотношениях некоторых из них определяет, кого из кошек любит каждый из котов.

Входные данные. В первой строке через пробел два натуральных числа N (количество котов и, соответственно, кошек) и M (количество утверждений об их взаимоотношениях). Будем считать, что N не превышает 15, а M не больше квадрата N. Далее следуют M строк с описанием взаимоотношений. Гарантируется, что решение существует и однозначно. При этом количество строк с утверждениями может быть избыточным.

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

Пример. При вводе таких данных
3 4
100-200
201-101
102-202
201-102
программа должна вывести
100 201
101 202
102 200