This problem can be rephrased as follows:

You are initially at a set $S_x$ containing $1$. You repeatedly advance to another set containing one or more common elements than your current set, until you reach a set containing $M$. At least how many moves are required?

The equivalence to the original problem is justified by that, for the final sets \(S_{a_1},S_{a_2},\dots,S_{a_k}\) containing \(1\) and \(M\), such a “path” always exists, and that the constraint is worse than the original problem.

If you try to solve the rephrased problem by naively adding edges and performing a BFS (Breadth-First Search), it costs \(\mathrm{O}(N^2)\) time, which does not fit in the limit. Instead, we use a technique that involves a virtual vertex.

We prepare \((N+M)\) vertices. The \(i\)-th (\(1 \le i \le N\)) vertex corresponds to set \(S_i\), and the \(j\)-th (\(N+1 \le j \le N+M\)) vertex corresponds to integer \((j-N)\). We add an edge of length \(1\) between vertex \(i\) and vertex \((j+N)\) if set \(S_i\) contains \(j\). Then, transitions to another set containing the same element are represented by \(\mathrm{O}(\sum A)\) edges. Note however that the answer is doubled, because moving as “set \(\rightarrow\) integer \(\rightarrow\) set” requires two edges.

All that left is to perform BFS on this graph. The complexity is \(\mathrm{O}(N+M+\sum A)\), because this is DFS on a graph with \((N+M)\) vertices and \(\sum A\) edges.