AT_ttpc2023_h 404 Chotto Found

$ N $ 個の文字列 $ S_1, S_2, \dots, S_N $ が与えられます。空でない文字列 $ T $ であって、以下の条件を満たすものの個数を求めてください。 - 文字列 $ S_1, S_2, \dots, S_N $ のうち、 $ T $ を (連続する) 部分文字列として含むものはちょうど $ 1 $ 個である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

答えを出力せよ。

### Sample Explanation 1 $ T = {} $ `a` の場合を考えると、 $ S_1 = {} $ `abc` と $ S_2 = {} $ `ca` の $ 2 $ 個が `a` を部分文字列として含むので、条件を満たしません。 $ T = {} $ `ab` の場合を考えると、 $ S_1 = {} $ `abc` のみが `ab` を部分文字列として含むので、条件を満たします。 $ T = {} $ `d` の場合を考えると、 $ S_1 = {} $ `abc` も $ S_2 = {} $ `ca` も `d` を部分文字列として含まないので、条件を満たしません。 条件を満たす文字列は $ T = {} $ `b`, `ab`, `bc`, `ca`, `abc` の $ 5 $ 個です。 ### Sample Explanation 2 $ T = {} $ `ab` の場合を考えると、 $ S_1 = {} $ `aab` と $ S_2 = {} $ `aab` の $ 2 $ 個が `ab` を部分文字列として含むので、条件を満たしません。 条件を満たす文字列はありません。 ### Sample Explanation 3 条件を満たす文字列は $ T = {} $ `a`, `b`, `ab`, `ba`, `aba` の $ 5 $ 個です。 ### Constraints - $ 1 \le N \le 10^5 $ - $ 1 \le |S_i| \le 10^6\ (1 \le i \le N) $ - $ \left(\sum_{i=1}^{N} |S_i|\right) \le 10^6 $ - $ S_i\ (1 \le i \le N) $ は英小文字からなる文字列