Optimizing Delivery Routes

You are given a collection of delivery routes. Each route is represented as a sequence of city names. Two routes are considered overlapping if they share at least one common city. The goal is to merge all overlapping routes into a single route so that the number of separate trips is minimized.

The merging process is defined as taking the union of the cities from two overlapping routes and then sorting the cities in lexicographical order. This process is repeated until no further merging can be done. For example, merging ["CityA", "CityB", "CityC"] and ["CityC", "CityD", "CityE"] yields ["CityA", "CityB", "CityC", "CityD", "CityE"].

Your task is to implement this optimization. Read the input from standard input and print the final merged routes to standard output, with each route on a new line.

inputFormat

The first line of input contains an integer N, the number of routes. Each of the following N lines contains a list of city names separated by spaces representing one route.

outputFormat

Output the optimized delivery routes, one per line. Each line should contain the sorted list of cities (in lexicographical order) for the corresponding merged route, separated by spaces.

## sample

3
CityA CityB
CityC CityD
CityE CityF

CityA CityB
CityC CityD
CityE CityF

</p>