首先每个串都必须是$S$的子序列，否则无解。
按长度从小到大依次考虑每个串，如果它两边都不能放，那么无解。
如果能放一边，那么放进去，把待定的全部放入另一边。
如果两边都能放，那么看看能否待定，如果不能则把它和待定的分别放入两边。
时间复杂度$O(nm)$。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 4005
int n,i,j,x,y,len[N],b[N],f[2][N],cnt[2],q[N],t;char a[N][N];
inline bool cmp(int x,int y){return len[x]<len[y];}
inline bool check(int x,int y){
if(len[x]>len[y])return 0;
for(int i=j=0;i<len[x];i++){
while(j<len[y]&&a[x][i]!=a[y][j])j++;
if(j==len[y])return 0;
j++;
}
return 1;
}
int main(){
scanf("%d",&n);
for(i=0;i<=n;i++){
scanf("%s",a[i]);
len[i]=strlen(a[i]);
b[i]=i;
if(!check(i,0))return puts("impossible"),0;
}
len[0]=0;
std::sort(b+1,b+n+1,cmp);
for(i=1;i<=n;i++){
x=check(f[0][cnt[0]],b[i]);
y=check(f[1][cnt[1]],b[i]);
if(!x&&!y)return puts("impossible"),0;
if(x&&!y){
f[0][++cnt[0]]=b[i];
for(j=1;j<=t;j++)f[1][++cnt[1]]=q[j];
t=0;
}
if(!x&&y){
f[1][++cnt[1]]=b[i];
for(j=1;j<=t;j++)f[0][++cnt[0]]=q[j];
t=0;
}
if(x&&y){
if(check(q[t],b[i]))q[++t]=b[i];
else{
f[0][++cnt[0]]=b[i];
for(j=1;j<=t;j++)f[1][++cnt[1]]=q[j];
t=0;
}
}
}
for(j=1;j<=t;j++)f[1][++cnt[1]]=q[j];
printf("%d %d
",cnt[0],cnt[1]);
for(i=1;i<=cnt[0];i++)puts(a[f[0][i]]);
for(i=1;i<=cnt[1];i++)puts(a[f[1][i]]);
return 0;
}