На плоскости расположена система из N одинаковых шестеренок, которая приводится в движение вращением шестеренки 1 по часовой стрелке. Сцепленные шестеренки могут вращаться только в разных направлениях.

Требуется определить направление вращения каждой шестеренки системы, либо установить, что систему заклинит.

Исходные данные программы: количество шестеренок N (1 ≤ N ≤ 100) и набор пар (i, j), которые определяют номера сцепленных шестеренок.

Например, для системы шестеренок, изображенной на рисунке, исходными данными будут число 5 и пары (1,2), (2,3), (4,5), (2,4), (3,5) Вывод программы может быть следующим:

шестеренка 1: по часовой стрелке
шестеренка 2: против часовой стрелки
шестеренка 3: по часовой стрелке
шестеренка 4: по часовой стрелке
шестеренка 5: против часовой стрелки