За последние 42 года Ваня успел совершить n кругосветных путешествий. В каждом путешествии он посещал некоторые города, а первые буквы названий записывал в порядке их посещения в своей записной книжке. И вот, в 2042 году Ваня решил вспомнить все свои путешествия. Однако он столкнулся с одной проблемой — городов, у которых совпадают первые буквы, очень много. А это значит, что точно восстановить каждое путешествие у него не удастся. Ваня не сильно расстроился, ведь все-равно он может извлечь из этого полезную информацию. Например, он может определить минимальное количество городов, которые он мог посетить за все n путешествий и подобрать названия для каждого из этих городов так, чтобы записи в его книжке были непротиворечивы.

Помогите Ване определить минимальное количество городов k, которые он мог посетить за последние 42 года совершив n кругосветных путешествий и подберите для каждого города некоторое название (возможно несуществующее). Так как Ваня и сам может придумать названия для городов, он просит каждому из городов сопоставить уникальное целое число из промежутка [1, k]. Также не забудьте определить для каждого путешествия номера городов, которые он мог посетить. В одном путешествии город может быть посещен несколько раз, но посещать город из самого себя нельзя.