실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
3023년, 지난 천년 동안 상당히 많은 소의 진화가 이루어졌고, 이로 인해 다양한 흥미로운 특성을 지닌 소가 탄생했습니다.
소의 진화 기록은 특별한 특징이 없는 기본 조상 소에서 시작하는 트리로 설명할 수 있습니다. 트리의 각 하위 수준에서는 모든 소가 새로운 특성 (예 : 반점이 있는 소는 모두 불을 뿜게 됨)을 가지게 진화하거나, 일부 소는 새로운 특성 (예 : 비행)으로 진화하고 일부 소는 진화하지 않는 다양한 변화가 일어납니다.
트리의 맨 아래에 있는 잎은 3023년의 모든 소의 하위 집단을 나타냅니다. 동일한 세트의 특성을 가진 잎(이하 하위 집단)은 없습니다. 예를 들어, 하위 집단 #1는 특별한 특성이 없는 소를 포함하고 있고, 하위 집단 #3는 텔레파시 비행 소를 포함하고 있습니다. 하위 집단 #2는 텔레파시를 가지지 않은 비행 소를 가지고 있습니다. 하위 집단 #3는 비행과 텔레파시 소의 조합으로 유일합니다.
위와 같은 진화 트리는 새로 진화한 각각의 특성이 트리의 정확히 한 가장자리에서 유래된 경우 '적절한' 진화 트리라고 합니다 (예 : 역사의 한 시점에서 진화한 경우). 예를 들어, 한 점이 두 개의 별도 가지에서 진화한 경우, 트리는 적절하지 않을 것입니다. 3023년에 소의 하위 인구에 대한 설명이 주어지면 이것이 적절한 진화 트리로 설명될 수 있는지 확인해주십시오.
입력의 첫 번째 줄은 하위 집단의 수 ()을 포함합니다. 다음 개의 각 줄은 하위 집단을 기술합니다. 줄은 정수 ()로 시작하고, 그 다음에는 해당 하위 집단의 모든 소의 특성들을 나타냅니다. 특성은 최대 20개의 소문자 문자열입니다 (a..z). 두 개의 하위 집단이 정확히 같은 특성을 가지는 경우는 없습니다.
이 하위 집단들의 기원을 설명하는 적절한 진화 트리를 형성하는 것이 가능하다면 "yes"를 출력하고, 그렇지 않다면 "no"를 출력하십시오.
4 2 spots firebreathing 0 1 flying 2 telepathic flying
yes
출처: USACO 2019 US Open Contest, Bronze Problem 3. Cow Evolution