Expert.
Put your skills to the test.

Problem summary

An undirected graph has uppercase labels on its vertices and may contain self-loops. Count vertex walks whose successive labels spell a given word. Vertices and streets may be revisited.

Constraints

4 ≤ N ≤ 100; target length at most 10; no parallel streets; the answer is at most 10000000.

Worked example

Official statement example.

6 8
POPOLO
1 2
2 3
3 3
3 4
4 5
5 6
6 1
2 5
POLO

12

Solution analysis

1. Let dp[v] count walks spelling the processed prefix and ending at v. For the first character set it to one exactly at vertices carrying that letter.
2. For each next character, traverse every adjacency and add dp[u] to next[v] only when v has the required label. Store a self-loop once: using that street once creates exactly one transition from its vertex back to itself.
3. In the sample, the first letter P allows vertices 1 and 3. Extending through O, then L, then O counts the distinct vertex sequences; summing the final endpoint counts gives 12.

Why it works

Induct on prefix length. Every walk for the next prefix has a unique preceding walk and final street, and the transition adds precisely these choices. Initialization counts all one-vertex walks, so summing the last layer counts every requested walk once.

Watch out. Walks are not required to be simple.,Do not insert a self-loop twice.

An independently written complete program with standard headers.

// Key idea: Induct on prefix length. Every walk for the next prefix has a unique preceding walk and
// final street, and the transition adds precisely these choices.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    string labels,word;
    cin>>labels;
    vector<vector<int>>adj(n);
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        --u;
        --v;
        adj[u].push_back(v);
        if(u!=v){
            adj[v].push_back(u);
        }
    }
    cin>>word;
    vector<long long>dp(n,0);
    for(int v=0;v<n;++v){
        dp[v]=labels[v]==word[0];
    }
    for(size_t i=1;i<word.size();++i){
        vector<long long>next(n,0);
        for(int u=0;u<n;++u){
            for(int v:adj[u]){
                if(labels[v]==word[i]){
                    next[v]+=dp[u];
                }
            }
        }
        dp.swap(next);
    }
    long long answer=0;
    for(long long count:dp){
        answer+=count;
    }
    cout<<answer<<'\n';
}