На заняттях шкільного гуртка Євгенію навчили виготовляти з паперу моделі правильних многогранників (платонових тіл) і напівправильних многогранників (архімедових тіл). Вона запам’ятала такі означення:
Платоновим тілом називають (опуклий) многогранник, у якому всі грані — правильні однакові многокутники, а многогранні кути при всіх вершинах однакові.
Архімедовим тілом називають (опуклий) многогранник, у якому всі грані — правильні многокутники (не обов’язково з однаковою кількістю сторін), а многогранні кути при всіх вершинах однакові. При цьому є щонайменше дві різні грані.
Таким чином, в архімедовому тілі грані кожного виду зустрічаються в тій самій кількості й у тій самій послідовності при обході навколо кожної вершини (чи для однакових, чи для протилежних напрямів обходу, якщо "дивитися ззовні").
Кілька моделей многогранників Євгенія виготовила для оформлення кабінету математики і прихопила додому, щоб вразити своїх рідних. Враження, звичайно, вона справила. Але, вечеряючи, недогледіла, як молодша сестра Марічка взялася розфарбовувати грані: кожну грань лише однією фарбою. При цьому кілька граней могли бути й одного кольору, навіть якщо вони були суміжними, тобто мали спільне ребро. Євгенія задумалась… Її, як майбутнього математика, зацікавило питання: скількома способами можна розфарбувати грані тіла Архімеда, маючи певну кількість фарб, з точністю до симетрій — рухів простору, що залишають многогранник на тому самому місці. Інакше кажучи, коли не розрізняють розфарбування, отримані одне з іншого взаємно однозначним відображенням граней при збереженні відношення суміжності.
Знаючи все про суміжність чи несуміжність граней тіла Платона чи Архімеда, визначте кількість розфарбувань цього многогранника для даної кількості кольорів.
У першому рядку вказано кількість фарб m (m < 6). Кількість вхідних рядків на 1 перевищує кількість граней многогранника і менша від 24. Усі грані многогранника занумеровано послідовними натуральними числами, починаючи з 1. j-й рядок (j > 1) містить (невпорядкований) перелік номерів граней, суміжних з гранню j – 1.
Вхідні дані гарантують, що кількість симетрій многогранника не перевищує 120.
Вивести кількість розфарбувань граней тіла, виконаних за допомогою m фарб і різних з точністю до симетрій многогранника.