解答：https://atcoder.jp/contests/abc302/submissions/41636421
解法：解説AC。
頂点1からNの後に、1からMまでの整数に対応する超頂点を導入する。どちらも0-indexに変換して、0~N-1を頂点に、N~N+M-1を超頂点に対応させる。また、集合Siが整数jを有する場合に、頂点i-1と超頂点N+j-1の間に無向辺を張る。すると当問題は、この拡張グラフの上でBFSを行い、超頂点Nから超頂点N+M-1に到達する最短距離を求める問題に変換することができる。
個人的に最短距離とマージ回数の関係が少し悩ましく感じた。仮にN→0→N+M-1と行けるのであれば、最短距離は2であり、マージ回数は0（集合S1が1とMとをどちらも有している）である。N→0→N+1→1→N+M-1であれば、最短距離は4であり、マージ回数は1（集合S1が1と2を有し、集合S2が2とMを有するため、集合S1と集合S2をマージ）である。
この考察（もう少し経路を増やしてもよい）より次のことが分かる。最短距離は超頂点→頂点→超頂点→頂点→超頂点…と、超頂点と頂点を繰り返しているが、最初の超頂点→頂点と最後の頂点→超頂点からの移動はマージ回数に影響せず、その間の移動はマージ回数のちょうど2倍となっている。よって、最短距離をdistとすると、(dist - 2) / 2がマージ回数となる。
