#include <bits/stdc++.h>
using namespace std;
struct trie{
    int id=0;
    char c;
    map<char,trie*> m;
    int e=0;
    trie *fail;
} *root=NULL;
int id=0;
void addtrie(string s){
    trie *p=root;
    for(int i=0;i<s.size();i++){
        if(p->m.count(s[i])==0) p->m[s[i]]=new trie;
        p=p->m[s[i]];
        if(p->id==0) p->id= ++id;
        p->c=s[i];
    }
    p->e++;
}
void buildactrie(){
    root->fail=NULL;
    queue<trie*> q;
    q.push(root);
    while(!q.empty()){
        trie *u=q.front();
        trie *t=u->fail;
        q.pop();
        for(auto i=u->m.begin();i!=u->m.end();i++){
            if(u==root) i->second->fail=root;
            else{
                t=u->fail;
                while(t!=NULL){
                    if(t->m.count(i->first)!=0){
                        i->second->fail=t->m[i->first];
                        break;
                    }
                    t=t->fail;
                }
                if(t==NULL) i->second->fail=root;
            }
            q.push(i->second);
        }
    }
}
void cxbl(trie *p){
    queue<trie*> q;
    q.push(p);
    while(!q.empty()){
        trie *u=q.front();
        q.pop();
        for(auto i=u->m.begin();i!=u->m.end();i++){
            q.push(i->second);
        }
        cout<<u->id<<" "<<u->c<<" ";
        if(u->fail!=NULL) cout<<u->fail->id;
        cout<<endl;
    }
}
int main(){
    string s[5]={"say","she","shr","he","her"};
    root=new trie;
    for(int i=0;i<5;i++) addtrie(s[i]);
    buildactrie();
    cxbl(root);
    return 0;
}