この問題は、以下のように言い換えることが出来ます。

初め、$1$ を含むある集合 $S_x$ にいる。ここから、今いる集合と同じ要素を $1$ 個以上含む集合に移動することを繰り返して、$M$ を含む集合へ移動する。最低で何回の移動が必要か？

この言い換えをしても答えが変わらないことは、最終的に \(1,M\) を含む集合としてマージされた集合 \(S_{a_1},S_{a_2},\dots,S_{a_k}\) には必ず上記のような移動方法が存在することと、元の問題より厳しい条件であるため答えが悪化しないことより示されます。

上記の問題は、愚直に辺を貼って BFS をしようとしても辺数が \(\mathrm{O}(N^2)\) あるため間に合いません。そこで超頂点というテクニックを用いて高速化をします。

用意する頂点は \(N+M\) 個です。\(1 \le i \le N\) 個目の頂点は、集合 \(S_i\) に対応します。\(N+1 \le j \le N+M\) 番目の頂点は、整数 \(j-N\) に対応します。そして、集合 \(S_i\) が \(j\) を含むとき、頂点 \(i\) と頂点 \(j+N\) 間に長さ \(1\) の辺を貼ります。 すると、同じ要素を含む別の集合に移動するということが \(\mathrm{O}(\sum A)\) 本の辺で表せます。ただし、集合 \(\rightarrow\) 整数 \(\rightarrow\) 集合と移動する際に辺を \(2\) 回使うため、答えが \(2\) 倍になってしまうことに注意してください。

あとはこのグラフ上で BFS をすればよいです。計算量は頂点数が \(N+M\)、辺数が \(\sum A\) のグラフでの BFS なので、\(\mathrm{O}(N+M+\sum A)\) です。