Four Plus Four

아직 제출이 없습니다시간 제한3초메모리 제한1024 MB

문제

Queen Marianna has three daughters, the princesses. Marianna keeps her royal seal in a safe. The safe is protected by a password: it is an eight-letter English word from the royal dictionary. The password changes every few days.

The Queen regularly goes on vacation, and in the meantime, the princesses learn to reign the kingdom. No one of them knows the password, however, Marianna wants any two princesses to be able to open the safe in case they have an agreement. For that, on three cards, she writes three keys: four-letter English words from the royal dictionary. Each key consists of the password letters: from the eight letters, four are selected and possibly rearranged, so that the result is a dictionary word. After that, the Queen puts the cards into a hat, and then the three princesses, in sequence, take a random card and keep it to themselves, not showing it to others.

Having the royal dictionary at hand, devise an arrangement for the Queen and the princesses so that, after Marianna hands out the keys, any two princesses could determine the password using the two keys they have.

힌트

Note that the last eight-letter word in the dictionary, "zyzzyvas", is an example of a word that can not be given as a password: from its letters, it is only possible to construct one key, "yays". Recall that a word can be given as a password only if at least three keys can be constructed from its letters. There are 7070 eight-letter words in the dictionary for which this condition does not hold.