ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Championship 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Interpreters

Time limit: 1.0 second
Memory limit: 64 MB
Problem illustration
To construct “Ural Guards” towers cheaply and rapidly building crews from many countries were invited. Of course developers were aware of the well-known tower of Babel fate and decided to hire some professional interpreters so building crews could communicate one another. Developers also settled if two crews are communicating then other crews must not understand a word because in that case other crew will listen instead of work and towers will not be constructed by the time.
Each crew speaks only one native language, but fortunately for any two languages it is possible to hire an interpreter who speaks them both. Unfortunately there is no interpreter who knows more then two languages, and so developers have to hire some of them. Your task is to determine the least number of interpreters to hire to allow any crew to communicate with any other.

Input

First line contains total number of building crews N (1 ≤ N ≤ 100). Following N lines contain languages each crew speaks — one language per line. Language is a non-empty sequence of small Latin letters and this sequence length does not exceed 10.

Output

In the first line you should print minimal number of interpreters. Following lines should contain languages they know in a form of “language1-language2”. If you cannot find a way to hire interpreters and to guarantee that no crews will waste time listening other crews communication then print the only word “Impossible”.

Sample

inputoutput
3
russian
french
german
3
russian-english
english-german
english-french
Problem Author: Sergey Pupyrev
Problem Source: The XIIth USU Programing Championship, October 6, 2007
To submit the solution for this problem go to the Problem set: 1571. Interpreters