P1019 [NOIP 2000 Senior] Word Chain (suspected erroneous problem)

注意：本题为上古 NOIP 原题，不保证存在靠谱的做法能通过该数据范围下的所有数据。本题的难度仅代表设计算法可以通过本题原始数据的难度。 本题为搜索题，本题不接受 hack 数据。[关于此类题目的详细内容](https://www.luogu.com.cn/paste/pf94n89x) NOIP2000 提高组 T3

Word chain is a game similar to the idiom chain we often play. We are given a set of words and a starting letter, and we are asked to find the longest "dragon" that starts with this letter. Each word may appear at most twice in the "dragon". When two consecutive words are connected, their overlapping part is merged into one. For example, `beast` and `astonish` become `beastonish` when chained. Moreover, the two adjacent parts must not have a containment relationship; for example, `at` and `atide` cannot be connected.

The first line contains a single integer $n$, the number of words. Each of the next $n$ lines contains one word. The last line contains a single character, which is the starting letter of the "dragon". You can assume that a "dragon" starting with this letter always exists.

Output only the length of the longest "dragon" that starts with this letter.

Sample explanation: the resulting "dragon" is `atoucheatactactouchoose`. Constraints: $n \le 20$. Translated by ChatGPT 5