#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull n,q,x_q[100005],y_q[100005],tot_w;
struct link_list{
    link_list*p_l=NULL,*p_r=NULL,*p_root;
    link_list(){p_root=this;}
    virtual void* self(){return this;}
};
link_list*find(link_list*p){return (p==p->p_root)?(p):(p->p_root=find(p->p_root));}
inline bool can_link(link_list*a,link_list*b){return ((a->p_r==b)&&(b->p_l==a))||(((a->p_r==NULL)&&(b->p_l==NULL))&&(find(a)!=find(b)));}
inline void link(link_list*a,link_list*b){(a->p_r=b),(b->p_l=a),(find(b)->p_root=find(a));}
struct node:link_list{
    node* s_[27];node**const son=s_-'a';
    static node d[],*cnt;
    int vis=-1;
    link_list l,r;
    inline void* operator new(size_t){return cnt++;}
    virtual void* self(){return this;}
};
node node::d[350005],*node::cnt=d,root;
struct str{
    static char c[],*cnt;
    char *p;
    inline void input(int i){
        (p=(cnt+=2));
        cin>>p;
        node*now=&root;
        for(;*cnt;cnt++) if(now->son[*cnt]) now=now->son[*cnt];else now=(now->son[*cnt]=new node);
        *cnt='{'; //'z'+1
        now=(now->son[*cnt]=new node);
        now->vis=i;
    }
}strs[40005];
char str::c[300005],*str::cnt=str::c;
inline bool can(str&a,str&b){
    char*pa=a.p,*pb=b.p;
    node*now=&root;
    for(;(*pa==*pb);pa++,pb++) now=now->son[*pa];
    node*now_a=now->son[*pa],*now_b=now->son[*pb];
    if(!can_link(now_a,now_b)) return false;
    for(pa++;*pa;pa++) if(!can_link(now_a->son[*pa],&now_a->r))return false;else now_a=now_a->son[*pa];
    for(pb++;*pb;pb++) if(!can_link(&now_b->l,now_b->son[*pb]))return false;else now_b=now_b->son[*pb];
    return true;
};
inline void add(str&a,str&b){
    char*pa=a.p,*pb=b.p;
    node*now=&root;
    for(;(*pa==*pb);pa++,pb++) now=now->son[*pa];
    node*now_a=now->son[*pa],*now_b=now->son[*pb];
    link(now_a,now_b);
    for(pa++;*pa;pa++) link(now_a->son[*pa],&now_a->r),now_a=now_a->son[*pa];
    for(pb++;*pb;pb++) link(&now_b->l,now_b->son[*pb]),now_b=now_b->son[*pb];
};
inline ull get_w(str&a,str&b){
    ull ans=0;
    for(char*pa=a.p,*pb=b.p;(*pa==*pb)&&(*pa!='{')&&(*pb!='{');pa++,pb++)ans++;
    return ans*ans;
}
vector<int> ans;
void dfs(node*p){
    if(p->vis>0){
        ans.push_back(p->vis);
        p=0;
        return ;
    }
    if(p->l.p_r)for(link_list*i=(p->l.p_r);(i!=NULL)&&(i!=&p->r);i=i->p_r)dfs((node*)i->self());
    for(auto j:p->s_)if((j!=NULL)&&(j->p_l==NULL))for(link_list*i=j;(i!=NULL)&&(i!=&p->r);i=i->p_r)dfs((node*)i->self());
}
stack<int> ans_q;
int cnt_ans_q;
int main(){
    cin>>n>>q;

    for(int i=1;i<=n;i++) strs[i].input(i);
    for(int i=1;i<=q;i++)cin>>x_q[i]>>y_q[i];
    for(int i=q;i>0;i--){
        if(can(strs[x_q[i]],strs[y_q[i]])){
            add(strs[x_q[i]],strs[y_q[i]]);
            ans_q.push(i);
        }
    }
    dfs(&root);
    for(int i=1,tot=ans.size();i<tot;i++){
        tot_w+=get_w(strs[ans[i-1]],strs[ans[i]]);
    }
    cout<<tot_w<<'\n';
    cout<<ans_q.size();
    for(;!ans_q.empty();ans_q.pop()) {
        cout<<' '<<ans_q.top();
    }
    cout<<'\n';
    for(auto i:ans){
        cout<<i<<' ';
    }
    return 0;
}