Tài xế tin cậy

Trong một buổi họp khu phố, FullHouse Dev được giao nhiệm vụ giúp tổ chức một hệ thống tài xế tin cậy cho cư dân. Vấn đề nảy sinh khi không phải tài xế nào cũng sẵn sàng đi đến mọi địa điểm trong khu vực, và người dân cần tìm ra cách di chuyển hiệu quả nhất với số lượng tài xế tin cậy tối thiểu.

Bài toán

Cho một mạng lưới các địa điểm và tài xế, mỗi tài xế chỉ phục vụ một số tuyến đường nhất định. Nhiệm vụ của FullHouse Dev là tìm ra số lượng tài xế tối thiểu cần thiết để có thể di chuyển giữa tất cả các địa điểm trong khu vực.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Mỗi test case bắt đầu với hai số nguyên \(a\) và \(b\):
  • \(a\) - số lượng địa điểm cần đến
  • \(b\) - số lượng tài xế
• \(b\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(m\) và \(n\) thể hiện tuyến đường mà tài xế phục vụ.

OUTPUT FORMAT:

• Với mỗi test case, in ra số lượng tài xế tối thiểu cần có để có thể di chuyển giữa tất cả các địa điểm.

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(2 \leq a \leq 1000\)
• \(1 \leq b \leq 1000\)
• \(m \neq n\), \(1 \leq m, n \leq b\)
• Đồ thị luôn liên thông.

Ví dụ

INPUT

1
3 3
1 2
2 3
1 3

OUTPUT

2

Giải thích

Trong ví dụ này, có 3 địa điểm và 3 tuyến đường. Chỉ cần 2 tài xế là đủ để di chuyển giữa tất cả các địa điểm. Ví dụ, có thể chọn tài xế phục vụ tuyến 1-2 và tài xế phục vụ tuyến 2-3, như vậy có thể đi đến tất cả các địa điểm thông qua việc kết hợp hai tuyến này.