부분집합

면접 대비

시간 제한1초메모리 제한128 MB

요약

집합 이름이 원소나 다른 집합 이름을 포함한다는 부등식이 주어질 때, 각 집합 이름이 반드시 가져야 하는 최소 원소 집합을 구한다.

문제

집합 부등식(집합 포함 관계)들이 주어졌을 때, 각 집합 이름이 반드시 가져야 하는 최소 원소 집합을 구하는 프로그램을 작성하세요.

집합 부등식은 X contains S 형태입니다. 여기서 $X$ 는 임의의 집합 이름이고, $S$ 는 집합 이름이거나 집합의 원소입니다.

집합 이름은 대문자 $A$ 부터 $Z$ 까지이고, 원소는 소문자 $a$ 부터 $z$ 까지입니다.

입력에 등장하는 각 집합 이름에 대해, 모든 부등식이 성립하도록 하는 가장 작은 원소 집합(최소 집합)을 구하세요.

첫째 줄에 집합 부등식의 개수 $N$ 이 주어집니다.

이어지는 $N$ 개의 줄에는 각각 하나의 집합 부등식이 X contains S 형식으로 주어집니다.

입력에 등장하는 모든 집합 이름을 알파벳 순서로 출력합니다. 각 집합 이름에 대해 그 최소 집합을, 원소들을 알파벳 순서로 나열하여 아래 형식으로 출력하세요.

이름 = {원소들}

예를 들어 집합 $A$ 의 최소 집합이 원소 $c$ 와 $d$ 로 이루어져 있다면 A = {c,d}와 같이 출력합니다. 원소가 하나도 없으면 Q = {}처럼 빈 중괄호를 출력합니다.

예제 1

입력

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

예상 출력

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