感觉这个题纯骗哥们，两年前强子来 bnds 讲时我还觉得无敌困难一个字没听懂，结果今天赵大哥又讲了这个题被 10min 速通了/xk

首先出度为 $0$ 的点一定是根，可以由此进行分层求出来原串长度以及每个结点代表的子串长度（感觉上就算给的是无向图也就是再分讨下就可以定出来 $\mathcal{O}(1)$ 个可行的根，然后后面还是一样了）。

然后你先考虑一下你能确定的东西的上限，你发现你无法区分原串与它的翻转，也无法把区分对字符集做一个双射的情况，然后我们相信除此以外我们一定能确定。

那首先对于长度为 $2$ 的子串你做到了这件事，对于长度为 $l>2$ 的，如果它入度为 $1$ 的话它一定是每个字符都一样的，然后也可以继承出它对应的颜色，否则设入点分别是 $x,y$，那 $x,y$ 的入点集至少有 $1$ 的交，如果交恰好是 $1$ 的话你也就定出来了两个的摆放方向，而交为 $2$ 的情况形成了长为 $l-2$ 的 border，也就是有长为 $2$ 的循环节，而且两种颜色可以从 $x,y$ 定出来，如果 $2|l$ 的话你还是定出来了它是某个串或其翻转，否则你需要确定它是形如 aba...ba 还是 bab...ab，先特判下全串是否有长为 $2$ 的循环节，其余的情况你总能让这两种串之一的边界碰到另一种颜色 $c$，在长度为 $l+1$ 的子串中找一下可以通过入点的交判断出来 a 还是 b 在边界上，于是就全确定出来了。

然后你就确定出来原串形如 s 或者 rev(s)，但是 s 只是每一位的等价类划分而非具体值，你贪心填一下然后比较 s 和 rev(s) 哪个小即可，时间复杂度线性。