Qəribə Rəngləmə

Sizə istiqamətsiz qraf G verilib. Bu qrafın kənarlarını 0, 1, 2, ... rəngləri ilə boyamalısınız ki:

1. Bütün kənarların rənglərinin cəmi mümkün olan ən kiçik qiymətə malik olsun.

2. Rəngi 0 olan hər bir kənar üçün, elə bir qonşu kənar mövcud olmalıdır ki, həmin kənarın rəngi 2 olsun. İki kənar, əgər ümumi bir təpəyə malikdirsə, qonşu hesab olunur.

Giriş verilənləri

Girişin ilk sətri testlərin sayını göstərir.

Hər bir test üçün əvvəlcə 1 ≤ n ≤ 20 və 1 ≤ m ≤ 30, yəni müvafiq olaraq təpələrin və kənarların sayı verilir. Sonrakı m sətirdə, hər sətirdə bir kənarın iki ucu göstərilir.

Çıxış verilənləri

Hər bir test üçün, verilən şərtlərə uyğun olaraq kənarların rənglərinin minimum cəmini çıxış edin.

Nümunələr