前言

好题，第一眼看根本就想不到二分图染色。

思路

一步一步来，先考虑只有一个栈的情况。

假设现在刚弹入了 $a_i$，那么满足以下性质：

1. 若存在 $i < j$ 且 $a_j < a_i$，那么 $a_i$ 不能现在就弹出来。
   反证法：如果现在就弹出，$a_j$ 必然后弹出，那么将不满足有序的条件，矛盾。

2. 同理，不存在这样的 $j$ 就应该立即弹出。

3. 通过性质二可以发现，弹出的顺序唯一。又因为必须按照顺序插入，所以插入的顺序也唯一。因此，整个操作序列唯一。

考虑完一个栈，再考虑有两个栈。
如果刚弹入了 $a_i$，且有 $i<j$，考虑什么情况下 $i$ 与 $j$ 不能再同一栈中。

性质：若存在一个 $k$，满足 $i<j<k$ 且 $a_k<a_i<a_j$，则 $i$ 与 $j$ 不能在同一个栈中。
反证法：如果在同一栈中，则 $i$ 一定在弹入 $j$ 之前先弹出。因为 $k$ 比 $j$ 晚弹入，则 $i$ 必定在 $k$ 之前弹出，不满足有序，矛盾。

因此，对于 $i<j$，如果存在这么一个 $k$，就 $i \to j$，即连边。
因为如果存在一个满足的序列的话，这个图一定是一个二分图。因为相连的边表示一个矛盾关系，两个点必定在不同的栈当中。同时，同一个栈中的点不存在矛盾关系。所以，这正好满足二分图的特征。

如果是一个二分图的话，就要输出字典序最小的序列。因为字典序最小，所以再考虑一下性质。

1. 因为要字典序最小，因此对于每一个数，能分到 $S_1$ 中就分到里面去。因此对于每一个数，划分到哪一个栈中是能确定的。
2. 在两个栈中，因为操作顺序唯一（见上），所以 $ab$ 与 $cd$ 相对顺序唯一。
3. 因为弹入哪一个栈里面唯一，所以 $ac$ 相对顺序唯一。
   比如：这个数弹入 $S1$ 中，下一个数弹入 $S2$ 中，输出为 $ac$。你不可能换成 $ca$，这肯定不行。
4. 同理，$bd$ 相对顺序唯一。

那我们就发现只有 $bc$ 与 $ad$ 相对顺序不唯一。因此，找到连续的 $bc$ 段或者 $ad$ 段，通过排序将字典序小的字符换到前面即可。
为什么要是_连续的 $bc$ 段或者 $ad$ 段呢_？举一个例子：$bccb$，这你可以随便换对吧。如果前面多插入一个 $a$ 呢？$abccb$？ $a$ 就只可以保持原位了。

因此，我们就大概做完了。

代码

咕咕咕，我写完了就放着上面。