問題文

N 頂点 M 辺の連結な単純無向二部グラフ G があります。 頂点には 1 から N までの番号が付いています。 i 本目の辺は頂点 U_i と頂点 V_i を結んでいます。

はじめ、各頂点は黒または白で塗られており、頂点 1 は黒で塗られています。 また、各辺の両端の色は異なります。この条件から全ての頂点の色は一意に定まります。

以下の操作を何回でも行うことができます。

• 頂点 A_1,A_2,\ldots,A_K のうち 1 つを選び v とする。G において v と同じ色の頂点からなる誘導部分グラフで、v と同じ連結成分に属する全ての頂点について、白黒を反転する。

全ての頂点を同じ色にするために必要な操作回数の最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \le T \le 10^4
• 2 \le N \le 2 \times 10^5
• N-1 \le M \le 2 \times 10^5
• 1 \le K \le \min(N, 10)
• 1 \le A_1 < A_2 < \ldots < A_K \le N
• 1 \le U_i < V_i \le N
• G は連結な単純無向二部グラフ
• 全てのテストケースにおける N の総和は 2 \times 10^5 以下
• 全てのテストケースにおける M の総和は 2 \times 10^5 以下
• 入力される値は全て整数

入力例 1

3
5 5 3
1 3 5
1 2
1 3
2 4
3 4
4 5
2 1 2
1 2
1 2
9 10 3
1 6 8
1 5
1 6
2 5
2 7
2 8
3 6
3 8
4 7
4 8
3 9

出力例 1

2
1
3

1 つ目のテストケースでは、はじめ、頂点 1,4 が黒、頂点 2,3,5 が白で塗られています。 以下の手順で操作を行うと、2 回の操作で全ての頂点を同じ色にすることができます。

• 頂点 3 を選ぶ。頂点 3 の色が黒に変わる。
• 頂点 1 を選ぶ。頂点 1,3,4 の色が白に変わる。