First, consider the following graph \(G\).

• Each vertex of \(G\) corresponds one-to-one with an already used product.
• For two (not necessarily distinct) vertices \(u\) and \(v\) of \(G\), there is an edge from vertex \(u\) to vertex \(v\) if and only if the second character of the product name corresponding to \(u\) coincides the first character of that for \(v\).

Then, each string in an NG list corresponds to a walk on \(G\).

Now the original problem is rephrased as follows: find the minimum number of elements in a tuple of walk on \(G\) such that every vertex of \(G\) is contained at least one of the walks.

Next, decompose \(G\) into strongly connected components (SCCs) to form the following directed graph \(G'\):

• Every vertex of \(G'\) corresponds one-to-one with an SCC of \(G\).
• For two distinct vertices \(u'\) and \(v'\), there is an edge from \(u'\) and \(v'\) if and only if one can reach from a vertex \(u\) in the SCC corresponding to \(u'\) to another \(v\) for \(v'\). Here, while the choices of \(u\) and \(v\) are not unique, by definition of SCC, note that the reachability is unique.

Then, one can prove that the number of directed paths in a minimum path cover is equal to the answer to the problem.
Here, a path cover of \(G'\) is a set of directed paths on \(G'\) such that every vertex of \(G'\) is contained in exactly one (directed path) of them; a minimum path cover is a path cover with the minimum number of elements (directed paths).

Thus, it is sufficient to solve a minimum path cover problem on \(G'\).
Here, since \(G'\) is obtained by decomposing \(G\) into SCCs, (removing self-loops and multi-edges,) and adding directed edges between reachable vertices, \(G'\) forms a DAG (Directed Acyclic Graph).
The minimum path cover problem on DAG can be solved by finding a maximum matching of a bipartite graph.
Specifically, denoting by \(N'\) the number of vertices in \(G'\), consider two \(N'\)-vertex sets \(U=\{U_1,U_2,\ldots,U_{N'}\}\) and \(V=\{V_1,V_2,\ldots, V_{N'}\}\), and add an edge between \(U_u\) and \(V_v\) if (and only if) \(G'\) has an edge from \(u\) to \(v\). Then the sought count is the size of a maximum matching between \(U\) and \(V\), subtracted from \(N'\).

Let \(K=26\) be the size of the alphabet. \(G\) has at most \(K^2\) vertices an \(K^3\) edges, so \(G'\) has at most \(K(K+1)/2\) vertices and \(K^2(K+1)^2/4\) edges. (The number of edges can be actually more strictly bounded by, for example, \((K+2)^4/24\).) Then, the construction of \(G\) and SCC decomposition costs \(O(K^3)\) time, the (naive) construction of the bipartite graph corresponding to \(G'\) costs \(O(K^6)\) time, and finding a maximum matching of the bipartite graph costs \(O(K^{16/3})\) time. While \(K^6\simeq 3\times 10^8\), the actual numbers of edges and vertices are half or quarter of them, so it is fast enough.
Therefore, the problem has been solved.

Sample code in 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;
}