Subsets

Interview

Time limit1sMemory limit128 MB

Summary

Given inequalities where a set name contains either an element or another set name, find each named set's minimal required elements.

Level: Medium5 of 10
Topics: Graph, DFS, Topological sort, Implementation
Solved: No attempts yet

Problem

Write a program that, given a collection of set inequalities, finds the minimal set of elements that each set name must take.

A set inequality has the form X contains S, where $X$ is any set name and $S$ is either a set name or a set element.

If $S$ is a set name, the inequality means that $X$ is a superset of or equal to $S$ , that is, $X \supseteq S$ .
If $S$ is an element, the inequality means that $X$ contains the element $S$ .

Set names are the uppercase letters $A$ through $Z$ , and elements are the lowercase letters $a$ through $z$ .

For each set name that appears in the input, determine its minimal set: the smallest set of elements the name must take so that all of the inequalities hold.

Input

The first line contains the number of set inequalities $N$ .

Each of the next $N$ lines contains one set inequality in the form X contains S.

Output

Print every set name that appears in the input, in alphabetical order. For each set name, print its minimal set with the elements listed in alphabetical order, using the format below.

Name = {elements}

For example, if the minimal set of $A$ consists of the elements $c$ and $d$ , print A = {c,d}. If a set has no elements, print empty braces, e.g. Q = {}.

Examples1

Example 1

Input

9
A contains B
A contains c
B contains d
F contains A
F contains z
X contains Y
Y contains X
X contains x
Q contains R

Expected output

A = {c,d}
B = {d}
F = {c,d,z}
Q = {}
R = {}
X = {x}
Y = {x}