RiseOJ – 소의 진화

설명

때는 3019년, 지난 천 년 동안 놀라울 만큼 많은 소의 진화가 일어나, 온갖 흥미로운 특징을 가진 소들이 생겨났다.

소의 진화 기록은 트리로 나타낼 수 있다. 트리의 루트에는 아무 특별한 특징이 없는 기본 조상 소가 있다. 트리의 각 자손 단계에서는, 모든 소가 새로운 특징을 진화시키거나(아래 그림의 불 뿜기처럼, 점박이 소들이 모두 불을 뿜게 된 경우), 소 개체군이 갈라져 일부 소는 새로운 특징(예: 비행)을 진화시키고 일부는 그렇지 않게 된다.

트리 맨 아래의 리프들은 3019년에 존재하는 모든 소 하위 개체군을 나타낸다. 동일한 특징 집합을 가진 리프(하위 개체군)는 없다. 예를 들어, 하위 개체군 #1은 특별한 특징이 없는 소들로 이루어져 있고, 하위 개체군 #3은 텔레파시를 쓰는 비행 소들로 이루어져 있다. 반면 하위 개체군 #2는 텔레파시를 쓰지 못하는 비행 소들이다. 하위 개체군 #3은 비행과 텔레파시의 조합에서 유일하다.

위와 같은 진화 트리에서, 새로 진화한 각 특징이 트리의 정확히 한 간선에서 비롯된(즉, 역사상 단 한 지점에서 생겨난) 경우 그 트리를 "올바른(proper)" 트리라고 한다. 예를 들어, 점박이 무늬가 서로 다른 두 가지에서 각각 생겨났다면 그 트리는 올바르지 않다. 3019년의 소 하위 개체군들에 대한 설명이 주어졌을 때, 이들이 올바른 진화 트리로 설명될 수 있는지 판별하시오.

문제 제공: Brian Dean

제약

문제 제공: Brian Dean

입력 형식

첫째 줄에 하위 개체군의 수 $$N$$ ( $2 \leq N \leq 25$ )이 주어진다. 다음 $$N$$ 개의 줄 각각은 하위 개체군 하나를 나타낸다. 각 줄은 정수 $$K$$ ( $0 \leq K \leq 25$ )로 시작하고, 이어서 그 하위 개체군의 모든 소가 가진 $$K$$ 개의 특징이 주어진다. 특징은 최대 20자의 소문자 (a..z)로 이루어진 문자열이다. 정확히 같은 특징들을 가진 두 하위 개체군은 없다.

출력 형식

이 하위 개체군들의 기원을 설명하는 올바른 진화 트리를 만들 수 있으면 "yes"를, 그렇지 않으면 "no"를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 evolution.in · 출력을 쓸 파일 evolution.out

예제 1

입력

4
2 spots firebreathing
0
1 flying
2 telepathic flying

출력

yes

설명

This example input corresponds to the proper tree shown in the diagram above.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > US Open > Bronze

올림피아드 > USACO > 2018-2019 > US Open > Bronze

태그

JudgeUSACO

소의 진화

평가 및 의견

풀이 제출