CF448B Suffix Structures

Bizon the Champion 不仅是一头普通的野牛，他还是“野牛队”的明星。 在一次比赛中，“野牛队”遇到了一个问题：“给定两个不同的单词 $s$ 和 $t$，需要将单词 $s$ 转换成单词 $t$。” 队员们认为这道题很简单，因为他们对后缀数据结构非常熟悉。Bizon Senior 擅长使用后缀自动机，他可以通过这种工具每次删除字符串中的一个字符。Bizon Middle 则对后缀数组了如指掌，他可以在字符串中任意交换两个字符。他们虽然对后缀树并不了解，但后缀树能够实现更多的功能。 Bizon the Champion 想知道“野牛队”能否完成这个任务。也许答案并不需要同时使用这两种数据结构。请判断他们是否能完成任务，如果能，是如何实现的？是只需要使用后缀自动机，还是只需用后缀数组，或者是需要两者兼用呢？注意，任何一种结构都可以无限次使用，且使用顺序不受限制。

第一行是一个非空单词 $s$。 第二行是一个非空单词 $t$。 注意，单词 $s$ 和 $t$ 互不相同。每个单词仅由小写英文字母组成，每个单词最多包含 100 个字母。

请在一行中输出答案。如果即便使用后缀数组和后缀自动机也无法将单词 $s$ 转换为单词 $t$，请输出 `need tree`。如果仅需要使用后缀自动机便可解决问题，请输出 `automaton`。如果只需使用后缀数组即可完成转换，则输出 `array`。如果需要同时使用这两种数据结构才能解决问题，请输出 `both`。 题目保证，如果问题可以只用后缀数组解决，那么只用后缀自动机是不能解决的。反之亦然。

在第三个样例中，你可以先利用后缀自动机删除第一个字符，把“both”变成“oth”，然后利用后缀数组进行两次交换得到“hot”。 **本翻译由 AI 自动生成**