Non-overlapping Gatherings

You are given a list of gatherings. Each gathering is described by a gathering name followed by a list of attendees. Two gatherings are considered overlapping if they share at least one common attendee. Your task is to choose a maximal set of gatherings such that no two selected gatherings have any overlapping attendees. The gatherings should be considered in lexicographical order (based on their names), and the output must be the list of selected gatherings sorted in lexicographical order. In the case where there are no gatherings, output an empty list.

Note: A gathering in the input is given as a string with the format GatheringName; Attendee1 Attendee2 .... The first line of input gives the number of gatherings.

inputFormat

The input is read from stdin and is structured as follows:

• The first line contains an integer n (n ≥ 0) representing the number of gatherings.
• The next n lines each contain a gathering description in the format: GatheringName; Attendee1 Attendee2 ....

outputFormat

Print the names of the selected non-overlapping gatherings in lexicographical order, separated by a single space, to stdout. If there are no valid gatherings, print an empty line.

3
Picnic; Alice Bob Charlie
Concert; Bob David
Workshop; Alice Eve

Concert Workshop