题解
对于维护「某些元素之间必须贴贴相邻」这样的问题，可以考虑使用一种叫做 PQTree 的结构来维护。
PQTree 上的点有三种类型：
- 叶子结点，表示一个元素
- P 类节点，表示这个节点的儿子的顺序是可以任意排布的
- Q 类节点，表示这个节点的儿子的顺序必须是当前给出的顺序或者逆序
现在我们考虑如何加入一个限制。设这一次限制是要求 $S$ 内的元素贴贴，那么我们把 $S$ 内对应的叶子都标记成黑色，将其他叶子标记成白色。对于非叶结点，如果它的子树内只有一种颜色的节点，那么它的颜色和这种颜色相同；否则认为这个点的颜色是灰色。
我们先求出每个点的颜色，然后考虑如何去 fix 这个限制。假设我们现在在考虑 $v$ 的子树，我们分类讨论一下：
- 如果 $v$ 不是灰色节点，那么下面的限制都已经满足了，直接返回
如果 $v$ 是灰色节点：
如果 $v$ 是 P 类节点：设 $v$ 的三种颜色的儿子的集合分别是 $v_B,v_W,v_G$（Black,White,Gray)
- 如果 $|v_G| = 1$ 且 $|v_B| = 0$：继续去 fix $v_G$ 内的元素，然后直接返回即可。
- 如果 $|v_G| > 2$，显然出现了矛盾，无解。
- 其余情况：考虑我们先清空 $v$ 的儿子集合，然后先往 $son_v$ 中加入 $v_W$ 中的所有节点，然后新建一个 Q 类节点 $n_1$，往 $son_v$ 中加入 $n_1$。然后先加入 $v_G$ 到 $son_{n_1}$，然后在 $son_{n_1}$ 中间插入一个新建的 P 类节点 $n_2$，然后令 $son_{n_2} = v_B$ 即可。我们发现这里需要限制这两个灰色节点白色全在左侧，黑色全在右侧（或相反），我们假设现在有一个分裂函数，可以把这个子树的点分裂成黑白部分，并同时保留所有可能，分裂成的子树的节点。我们只需要将 $v_G$ 中的点换成对应的 vector 就好了。
如果 $v$ 是 Q 类节点：
- 找到最左边和最右边的非白色节点位置 $l,r$，位置指的是 $son_v$ 的相对位置编号。
- 如果 $[l+1,r-1]$ 内有非黑色节点，无解。
- 如果没有黑色节点，只有一个灰色节点，递归 fix 这个灰色节点然后返回。
- 否则只需要将 $l,r$ 位置的节点看情况分裂（只有灰色需要分裂）。
所以现在重点是如何实现这个分裂函数 $v$，WLOG，我们想将 $v$ 分裂成左边全是白色，右边全是黑色的森林。并且我们不能丢失所有可能的顺序关系（所以直接拆开是不可以的），根据上面过程的启发可以得到类似的过程：
- 如果 $v$ 不是灰色节点，直接返回当前子树。
如果 $v$ 是灰色节点：
如果 $v$ 是 P 类节点：设 $v$ 的三种颜色的儿子的集合分别是 $v_B,v_W,v_G$（Black,White,Gray)
- 如果 $|v_G| > 1$，显然无解。
- 否则我们一定是形如，左边是一堆没有顺序关系限制的 $v_W$ 内的点，中间可能是一个 $v_G$，然后右边是没有顺序关系限制的 $v_B$ 中的点。所以我们先新建两个 P 类节点 $n_1,n_2$，$son_{n_1} = v_W,son_{n_2} = v_B$，然后再递归处理 $v_G$ 的分裂情况（如果有的话），最后按照顺序拼起来就好了。最后不要忘记删除节点 $v$。
如果 $v$ 是 Q 类节点：
- 如果不存在一种顺序（正序和反序），满足排布形式形如白-灰-黑，显然无解。
- 如果灰色点数量 $>1$，显然无解。
- 否则我们只需要递归分裂灰色节点即可。
- 最后不要忘记删除 $v$ 点
分析一下复杂度：假设有 $n$ 个元素，$m$ 次操作。看起来我们每次需要新建很多节点，复杂度会自闭。但是注意到我们可以缩起来所有的链（很多关于树的复杂度用缩小度点和链，环很好用），这样由于叶子永远只有 $n$ 个，那么非叶子节点数量也是 $O(n)$ 的（实际上会有 $n-1$ 个），复杂度就是 $O(nm)$。
具体实现缩链的时候，我们用一个 dfs，每次对于 $v$ 的所有儿子，都一直往下跳到第一个不是链的位置，并将他们全都缩起来。这样可能会处理不好根连出的一条链，但是可以特判（虽然我的代码没判）
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1e5 + 5;
int typ[MAXN],col[MAXN];
std::vector<int> G[MAXN];
int bin[MAXN],tp,tot;
int n,m;
inline void run(){
puts("-1");
exit(0);
}
inline int New(int o){
int v = tp ? bin[tp--] : ++tot;
typ[v] = o;return v;
}
inline void del(int v){
G[v].clear();bin[++tp] = v;
}
inline bool chk(std::vector<int> &vec){
int ps = -1;
FOR(i,0,SZ(vec)-1) if(col[vec[i]] == 2){
if(ps != -1) return 0;
ps = i;
}
if(ps == -1){
FOR(i,0,SZ(vec)-1) if(col[vec[i]]){ps = i;break;}
}
FOR(i,0,ps-1) if(col[vec[i]] != 0) return 0;
FOR(i,ps+1,SZ(vec)-1) if(col[vec[i]] != 1) return 0;
return 1;
}
inline std::vector<int> split(int v){// 左0右1
if(col[v] <= 1) return {v};
if(typ[v]){// Q
if(!chk(G[v])) std::reverse(all(G[v]));
if(!chk(G[v])) run();
std::vector<int> res;
for(auto x:G[v]){
if(col[x] != 2) res.pb(x);
else{
std::vector<int> tmp = split(x);
res.insert(res.end(),all(tmp));
}
}
del(v);
return res;
}
else{// P
std::vector<int> son[3];
for(auto x:G[v]) son[col[x]].pb(x);
if(SZ(son[2]) > 1) run();
std::vector<int> res;
if(SZ(son[0])){
int n0 = New(0);G[n0] = son[0];
res.pb(n0);
}
if(SZ(son[2])){
std::vector<int> tmp = split(son[2][0]);
res.insert(res.end(),all(tmp));
}
if(SZ(son[1])){
int n1 = New(0);G[n1] = son[1];
res.pb(n1);
}
del(v);
return res;
}
}
inline void work(int v){
if(col[v] <= 1) return;
if(typ[v]){// Q
int l = 1e9,r = -1e9;
FOR(i,0,SZ(G[v])-1) if(col[G[v][i]]) l = std::min(l,i),r = std::max(r,i);
FOR(i,l+1,r-1) if(col[G[v][i]] != 1) run();
if(l == r && col[G[v][l]] == 2){
work(G[v][l]);
return;
}
std::vector<int> son;
FOR(i,0,l-1) son.pb(G[v][i]);
if(col[G[v][l]] == 2){
std::vector<int> tmp = split(G[v][l]);
son.insert(son.end(),all(tmp));
}
else son.pb(G[v][l]);
FOR(i,l+1,r-1) son.pb(G[v][i]);
if(l != r){
if(col[G[v][r]] == 2){
std::vector<int> tmp = split(G[v][r]);
std::reverse(all(tmp));
son.insert(son.end(),all(tmp));
}
else son.pb(G[v][r]);
}
FOR(i,r+1,SZ(G[v])-1) son.pb(G[v][i]);
G[v] = son;
}
else{// P
std::vector<int> son[3];
for(auto x:G[v]) son[col[x]].pb(x);
if(son[1].empty() && SZ(son[2]) == 1){
work(son[2][0]);
return;
}
G[v].clear();
if(SZ(son[2]) > 2) run();
G[v] = son[0];
int n1 = New(1);G[v].pb(n1);
if(SZ(son[2]) >= 1){
std::vector<int> tmp = split(son[2][0]);
G[n1].insert(G[n1].end(),all(tmp));
}
if(SZ(son[1])){
int n2 = New(0);
G[n1].pb(n2);
G[n2] = son[1];
}
if(SZ(son[2]) >= 2){
std::vector<int> tmp = split(son[2][1]);
std::reverse(all(tmp));
G[n1].insert(G[n1].end(),all(tmp));
}
}
}
char str[MAXN];
inline void apply(int v){
if(v >= 2 && v <= m+1){
col[v] = (str[v-1]=='1');
return;
}
int c0 = 0,c1 = 0;
for(auto x:G[v]){
apply(x);
if(col[x] == 0) c0 = 1;
else if(col[x] == 1) c1 = 1;
else c0 = c1 = 1;
}
if(c0 && !c1) col[v] = 0;
else if(!c0 && c1) col[v] = 1;
else col[v] = 2;
}
inline void gao(int v){
for(auto &x:G[v]){
int t = x;
while(SZ(G[t]) == 1){
int p = t;
t = G[t][0];
del(p);
}
x = t;gao(x);
}
}
inline void dfs(int v){
if(v >= 2 && v <= m+1){
printf("%d ",v-1);
return;
}
for(auto x:G[v]) dfs(x);
}
int main(){
scanf("%d%d",&n,&m);
int rt = New(0);
FOR(i,1,m) G[rt].pb(New(0));
FOR(i,1,n){
scanf("%s",str+1);
apply(rt);
work(rt);
gao(rt);
}
dfs(rt);puts("");
return 0;
}
