[BalticOI 2014 Day1] Three Friends
题目描述
有一个字符串 $S$，对他进行操作：
1. 将 $S$ 复制为两份，存在字符串 $T$ 中
2. 在 $T$ 的某一位置上插入一个字符，得到字符串 $U$
现在给定 $U$，求 $S$。
输入输出格式
输入格式
第一行一个整数 $N$ 代表 $U$ 的长度。
第二行 $N$ 个字符代表字符串 $U$。
输出格式
- 如果不能通过上述的步骤从 $S$ 推到 $U$，输出 `NOT POSSIBLE`。
- 如果从 $U$ 得到的 $S$ 不是唯一的，输出 `NOT UNIQUE`。
- 否则，输出一个字符串 $S$。
输入输出样例
输入样例 #1
7
ABXCABC输出样例 #1
ABC输入样例 #2
6
ABCDEF输出样例 #2
NOT POSSIBLE输入样例 #3
9
ABABABABA输出样例 #3
NOT UNIQUE说明
#### 数据规模与约定
**本题采用捆绑测试。**
- Subtask 1（35 pts）：$N \le 2001$。
- Subtask 2（65 pts）：无特殊限制。
对于 $100\%$ 的数据，$2 \le N \le 2 \times 10^6+1$，保证 $U$ 中只包含大写字母。
#### 说明
翻译自 [BalticOI 2014 Day1 B Three Friends](https://boi.cses.fi/files/boi2014_day1.pdf)。