Problem M
Breaking Bad

Walter was once a promising chemist. Now he teaches high school students chemistry, and was recently diagnosed with lung cancer. In both desperation and excitement he decides to use his chemistry skills to produce illegal drugs and make quick money for his family. He forms a partnership with one of his old students, Jesse, who has some experience with the drug scene.

Now Walter and Jesse are preparing for their first “cook” (the process of making the drugs). They have a list of items they need for the cook, but they realized they have to be very careful when going to the store. The reason is that it may be suspicious to buy certain pairs of items, like cold medicine and battery acid, in the same trip.

They decide to divide the items among themselves, so that each of them can go one trip to the store and buy their share of items without the risk of anyone becoming suspicious. Help them find such a division, or tell them that it is not possible.

Input

The first line of input contains an integer $N$, $1 \leq N < 100\, 000$, the number of items they want to buy. The following $N$ lines contain the names of these items, all of which are different. A name consists of at most $20$ lowercase letters from the English alphabet or underscores, and is non-empty. The next line of input contains an integer $M$, $0 \leq M < 100\, 000$, the number of pairs of items that are considered suspicious when bought together. Then follow $M$ lines, each containing the names of two different items that form a suspicious pair. Each suspicious pair will be listed exactly once.

Output

If it is possible for Walter and Jesse to divide the items among themselves, then output two lines. In the first line output the names of the items that Walter should buy. In the second line output the names of the items that Jesse should buy. If there are multiple solutions, output any of them. If this is not possible, output impossible.

5
battery_acid
drain_cleaner
antifreeze
cold_medicine
lantern_fuel
2
cold_medicine battery_acid
antifreeze lantern_fuel

lantern_fuel drain_cleaner battery_acid
antifreeze cold_medicine

3
fuel
lighter
knife
3
fuel lighter
lighter knife
knife fuel

impossible