Для возведения башен комплекса Стражи Урала приглашены строительные бригады
из разных стран. Такое нововведение, по замыслу владельцев, позволит
построить небоскрёбы за более короткие сроки и меньшую стоимость. Для того
чтобы Стражи Урала не постигла участь другой известной многоэтажки —
Вавилонской башни — на строительную площадку решили привлечь
профессиональных переводчиков. С их помощью строители разных бригад
должны иметь возможность общаться друг с другом. Единственное
ограничение — любой разговор должен быть строго конфиденциальным, т.е.
никая другая бригада не должна понять его суть.
Известно, что можно нанять переводчика, знающего любые два языка. Строители бригады
говорят только на своём родном языке. Попробуйте определить, какое минимальное
количество переводчиков требуется для строительства небоскрёбов.
Исходные данные
В первой строке находится количество строительных бригад N (1 ≤ N ≤ 100).
Каждая из последующих N строк содержит название языка (непустая последовательность из не более чем
10 строчных латинских букв), на котором говорят строители бригады.
Результат
В первой строке выведите требуемое количество переводчиков, в последующих — языки,
на которых они говорят в формате «язык1-язык2». Если обеспечить конфиденциальные
разговоры не получится, то выведите «Impossible».
Пример
исходные данные | результат |
---|
3
russian
french
german
| 3
russian-english
english-german
english-french
|
Автор задачи: Сергей Пупырев
Источник задачи: XII Чемпионат УрГУ по программированию, 6 октября, 2007