Romeo và Juliet cuối cùng đã quyết định kết hôn. Nhưng việc chuẩn bị tiệc cưới diễn ra không được suôn sẻ cho lắm, vì ai cũng biết rằng quan viên hai họ: Montesco và Capuleto có mối thù sâu đậm. Bạn sẽ cần phải chọn xem nên mời người nào và không nên mời người nào để ngăn chặn những mâu thuẫn.

Bạn sẽ có một danh sách ~n~ người có thể được mời đến bữa tiệc hoặc không. Với người thứ ~i~, bạn lại có danh sách các kẻ thù của người đó: ~e_1, e_2, ..., e_{p_i}~.

Mối quan hệ thù hằn này có hai tính chất như sau:

• Nếu ~a~ là kẻ thù của ~b~, và ~b~ là kẻ thù của ~c~ thì ~a~ là bạn của ~c~. Đồng thời kẻ thù của ~c~ cũng sẽ trở thành kẻ thù của ~a~.
• Nếu ~a~ là kẻ thù của ~b~ thì ~b~ cũng là kẻ thù của ~a~ (kể cả khi ~a~ không nằm trong danh sách kẻ thù trực tiếp của ~b~).

Một người sẽ chỉ chấp nhận tới dự đám cưới khi và chỉ khi tất cả bạn bè của anh ta được mời và tất cả kẻ thù của anh ta đều không tham dự.

Nhiệm vụ của bạn là tối đa hóa số người có thể được mời.

Ví dụ, nếu ~n = 5~ và ta biết rằng: ~1~ là kẻ thù của ~3~, ~2~ là kẻ thù của ~1~ và ~4~ là kẻ thù của ~5~, như vậy ta có thể mời tối đa 3 người. Những người này có thể là ~2, 3~ và ~4~.

Input

• Dòng thứ nhất gồm số nguyên dương ~t~ miêu tả số test case.
• Đối với mỗi test case:
  • Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả số người cần được xem xét.
  • ~n~ dòng sau, dòng thứ ~i~: đầu tiên có một số nguyên ~p~ miêu tả số kẻ thù trực tiếp mà người thứ ~i~ có, sau đó là ~p~ số nguyên dương miêu tả kẻ thù của người thứ ~i~.

Output

• Với mỗi test case, in ra số lượng người lớn nhất có thể mời.

Constraints

• ~1 \le t \le 20~
• ~1 \le k < n\le 200~.

Sample Input 1:

3
5
1 3
1 1
0
1 5
0
8
2 4 5
2 1 3
0
0
0
1 3
0
1 5
3
2 2 3
1 3
1 1

Sample Output 1:

3
5
0

Cho đồ thị vô hướng, gồm ~n~ đỉnh và ~m~ cạnh, mỗi đỉnh sẽ có một trọng số.

Hãy tìm một đường đi từ ~1~ tới ~n~ sao cho chênh lệch lớn nhất giữa trọng số của hai đỉnh liền kề trên đường đi là nhỏ nhất có thể.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, 1 \le m \le 2*10^5)~
• ~n~ dòng sau, mỗi dòng gồm ~n~ số nguyên dương ~c_i~ là trọng số của đỉnh thứ ~i~ ~(1 \le c_i \le 10^9)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~u_i,v_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i)~ - miêu tả cạnh ~(u_i,v_i)~.

Output:

• In ra chênh lệch lớn nhất giữa trọng số của hai đỉnh liền kề trên đường đi sao cho nó nhỏ nhất có thể.

Constraints:

• Có ~50\%~ số test ứng với ~n \le 2*10^3~
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

3 3
1 2 3
1 2
2 3
1 3

Output 1

1

Explanation 1:

Đi đường ~(1,2,3)~ thay vì ~(1,3)~.

Cho đồ thị đầy đủ vô hướng có trọng số (nghĩa là đồ thị gồm ~\frac{n*(n-1)}{2}~ cạnh phân biệt), trong đó có ~m~ cạnh có trọng số là ~1~, các cạnh còn lại có trọng số là ~0~.

Hãy tìm cây khung nhỏ nhất của đồ thị này.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, 1 \le m \le min(4*10^5,\frac{n*(n-1)}{2}))~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~u_i,v_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i)~ - miêu tả cạnh ~(u_i,v_i)~ có trọng số là ~1~.

Output:

• Trọng số của cây khung nhỏ nhất của đồ thị.

Constraints:

• Có ~50\%~ số test ứng với ~n \le 2*10^3~
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6

Output 1

2

Input 2

3 0

Output 2

0