파일 업로드

소의 진화

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

3023년, 지난 천년 동안 상당히 많은 소의 진화가 이루어졌고, 이로 인해 다양한 흥미로운 특성을 지닌 소가 탄생했습니다.

소의 진화 기록은 특별한 특징이 없는 기본 조상 소에서 시작하는 트리로 설명할 수 있습니다. 트리의 각 하위 수준에서는 모든 소가 새로운 특성 (예 : 반점이 있는 소는 모두 불을 뿜게 됨)을 가지게 진화하거나, 일부 소는 새로운 특성 (예 : 비행)으로 진화하고 일부 소는 진화하지 않는 다양한 변화가 일어납니다.

트리의 맨 아래에 있는 잎은 3023년의 모든 소의 하위 집단을 나타냅니다. 동일한 세트의 특성을 가진 잎(이하 하위 집단)은 없습니다. 예를 들어, 하위 집단 #1는 특별한 특성이 없는 소를 포함하고 있고, 하위 집단 #3는 텔레파시 비행 소를 포함하고 있습니다. 하위 집단 #2는 텔레파시를 가지지 않은 비행 소를 가지고 있습니다. 하위 집단 #3는 비행과 텔레파시 소의 조합으로 유일합니다.

위와 같은 진화 트리는 새로 진화한 각각의 특성이 트리의 정확히 한 가장자리에서 유래된 경우 '적절한' 진화 트리라고 합니다 (예 : 역사의 한 시점에서 진화한 경우). 예를 들어, 한 점이 두 개의 별도 가지에서 진화한 경우, 트리는 적절하지 않을 것입니다. 3023년에 소의 하위 인구에 대한 설명이 주어지면 이것이 적절한 진화 트리로 설명될 수 있는지 확인해주십시오.

💻 입력

입력의 첫 번째 줄은 하위 집단의 수 NN (2N252 \leq N \leq 25)을 포함합니다. 다음 NN개의 각 줄은 하위 집단을 기술합니다. 줄은 정수 KK (0K250 \leq K \leq 25)로 시작하고, 그 다음에는 해당 하위 집단의 모든 소의 KK 특성들을 나타냅니다. 특성은 최대 20개의 소문자 문자열입니다 (a..z). 두 개의 하위 집단이 정확히 같은 특성을 가지는 경우는 없습니다.

🖨️ 출력

이 하위 집단들의 기원을 설명하는 적절한 진화 트리를 형성하는 것이 가능하다면 "yes"를 출력하고, 그렇지 않다면 "no"를 출력하십시오.


💻 예제 입력 1
4
2 spots firebreathing
0
1 flying
2 telepathic flying
🖨️ 예제 출력 1
yes

출처: USACO 2019 US Open Contest, Bronze Problem 3. Cow Evolution