まず、次のような有向グラフ \(G\) を考えます。

• \(G\) の頂点はすでに使用されている商品と一対一に対応する。
• （相異なるとは限らない）\(G\) の頂点 \(u\), \(v\) について、\(u\) に対応する商品名の \(2\) 文字目と \(v\) に対応する商品名の \(1\) 文字目が一致するとき、かつその時に限り頂点 \(u\) から頂点 \(v\) へ有向辺を張る。

このとき、NGリストの各文字列は \(G\) 上の歩道と対応させることができます。

このとき、元の問題は、「 \(G\) 上の歩道の組であって、\(G\) の任意の頂点が \(1\) つ以上の歩道に含まれているものについて、組に含まれる歩道の数としてあり得る最小の値を求めよ。」と言い換えることができます。

次に \(G\) について強連結成分分解を行い、それをもとにした次の有向グラフ \(G'\) を考えます。

• \(G'\) の頂点は \(G\) の強連結成分と一対一に対応する。
• \(G'\) の 相異なる頂点 \(u'\), \(v'\) についてそれぞれに対応する強連結成分に属する \(G\) 上の頂点 \(u,v\) について\(u\) から \(v\) へ \(G\) 上で（\(1\) 本以上の辺を通って）到達可能であるとき、かつそのときに限り \(u'\) から \(v'\) へ有向辺を張る。ここで、\(u, v\) の選び方は強連結成分に対して一意でないが、強連結成分の定義より、到達可能であるかは一意であることに注意する。

このとき、\(G'\) における最小道被覆の有向道の数が問題の答えと一致することが証明できます。
ここで、グラフ \(G'\) 上の道被覆とは\(G'\) 上の有向道の集合であって、\(G'\) 上のすべての頂点がそのうちのちょうど \(1\) つ（の有向道）に含まれるようなものをさし、最小道被覆は道被覆のうち、要素数（属する有向道の数）が最小となるものをさします。

よって、\(G'\) 上での最小道被覆問題を解けば良いです。
ここで、\(G'\) は \(G\) を強連結成分分解した後のグラフについて、（自己ループ及び多重辺を取り除き）到達可能な頂点の間に新たに有向辺を張ったものであるので、\(G'\) はDAG となっています。 DAG上の最小道被覆問題は二部グラフの最大マッチングを求めることによって解くことができます。
具体的には、\(G'\)の頂点数を \(N'\) として、\(2\) つの \(N'\) 頂点からなる集合 \(U=\{U_1,U_2,\ldots,U_{N'}\}\), \(V=\{V_1,V_2,\ldots, V_{N'}\}\) を考え、\(G'\) 上で頂点 \(u\) から頂点 \(v\) への辺が存在するとき（かつそのときに限り）\(U_u\) と \(V_v\) を結んだときの \(U,V\) 間の最大マッチングの数を \(N'\) から引いたものが答えとなります。

アルファベットの数を\(K=26\) として、\(G\) の頂点数は高々 \(K^2\), 辺の数は高々 \(K^3\) であり、 \(G'\) の頂点数は高々 \(K(K+1)/2\), 辺の数は \(K^2(K+1)^2/4\) です。（\(G'\) の辺数は実際はもっと厳しく\((K+2)^4/24\)などで評価できます） このとき、\(G\) の構成および強連結成分分解には高々 \(O(K^3)\), \(G'\) に対応する二部グラフの構成は愚直に行えば \(O(K^6)\), 二部グラフの最大マッチングを求めるには \(O(K^{16/3})\) の計算量がかかります 。ここで、\(K^6\simeq 3\times 10^8\) ですが、実際には頂点数や辺数はそれらの\(1/2\) や \(1/4\) 以下であるため十分高速です。
よって、この問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>
#include <atcoder/scc>
#include <atcoder/maxflow>
using namespace std;
using namespace atcoder;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define N 676

int main(void){
	int n,m,sz;
	string s[N];
	vector<vector<int> > scc;
	int grp[N];
	bool r[N][N];

	cin>>n;
	rep(i,n)cin>>s[i];
	scc_graph g1(n);
	rep(i,n)rep(j,n){
		if(s[i][1]==s[j][0])g1.add_edge(i,j);
	}
	scc=g1.scc();
	m=scc.size();
	rep(i,m){
		sz=scc[i].size();
		rep(j,sz){
			grp[scc[i][j]]=i;
		}
	}

	rep(i,n)rep(j,n){
		if(s[i][1]==s[j][0]){
		  r[grp[i]][grp[j]]=true;
		}
	}
	for(int i=m-1;i>=0;i--){
		for(int j=i+1;j<m;j++){
			if(r[i][j]){
				for(int k=j+1;k<m;k++){
					r[i][k]|=r[j][k];
				}
			}
		}
	}

	mf_graph<int> g2(2*m+2);
	for(int i=0;i<m;i++){
		g2.add_edge(0,i+1,1);
		g2.add_edge(i+m+1,2*m+1,1);
	}
	for(int i=0;i<m;i++){
		for(int j=i+1;j<m;j++){
			if(r[i][j])g2.add_edge(i+1,j+m+1,1);
		}
	}

	cout<<(m-g2.flow(0,2*m+1))<<endl;
	return 0;
}