시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1513 946 749 66.108%

문제

상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 

하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.

이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 도시들을 여행할 수 있도록 도와주자.

상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

입력

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,

각 테스트 케이스마다 다음과 같은 정보가 주어진다.

  • 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다.
  • 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b) 
  • 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.

출력

테스트 케이스마다 한 줄을 출력한다.

  • 상근이가 모든 도시를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.

예제 입력 1

2
3 3
1 2
2 3
1 3
5 4
2 1
2 3
4 3
4 5

예제 출력 1

2
4
W3sicHJvYmxlbV9pZCI6IjkzNzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjNWVjXHVkNTg5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhY2E4XHVjNmI4XHViYzI5XHVkNTU5XHVjNzQ0IFx1YjlkZVx1YzU0NCBOXHVhYzFjXHVhZDZkXHVjNzQ0IFx1YzVlY1x1ZDU4OVx1ZDU1OFx1YmE3NFx1YzExYyZuYnNwO1x1Yzc5MFx1YzU0NFx1Yjk3YyBcdWNjM2VcdWFlMzBcdWI4NWMgXHViOWM4XHVjNzRjXHViYTM5XHVjNWM4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJlNDRcdWQ1ODlcdWFlMzBcdWI5N2MgXHViYjM0XHVjMTFjXHVjNmNjXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjZDVjXHViMzAwXHVkNTVjIFx1YzgwMVx1Yzc0MCBcdWM4ODVcdWI5NThcdWM3NTggXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1ZDBjMFx1YWNlMCBcdWFkNmRcdWFjMDBcdWI0ZTRcdWM3NDQgXHVjNzc0XHViM2Q5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViYzg4IFx1YmMyOVx1ZDU1OSBcdWIzZDlcdWM1NDhcdWM3NTggXHViZTQ0XHVkNTg5IFx1YzJhNFx1Y2YwMFx1YzkwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgPHN0cm9uZz5cdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1Yzg4NVx1Yjk1ODxcL3N0cm9uZz5cdWM3NTggXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1ZDBjMFx1YWNlMCBcdWJhYThcdWI0ZTAgXHViM2M0XHVjMmRjXHViNGU0XHVjNzQ0IFx1YzVlY1x1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwJm5ic3A7XHVkNTVjIFx1YWQ2ZFx1YWMwMFx1YzVkMFx1YzExYyBcdWIyZTRcdWI5NzggXHVhZDZkXHVhYzAwXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGMgXHViMmU0XHViOTc4IFx1YWQ2ZFx1YWMwMFx1Yjk3YyBcdWFjNzBcdWNjZDAgXHVhYzAwXHViM2M0KFx1YzJlY1x1YzljMFx1YzViNCBcdWM3NzRcdWJiZjggXHViYzI5XHViYjM4XHVkNTVjIFx1YWQ2ZFx1YWMwMFx1Yjc3Y1x1YjNjNCkgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVChUJm5ic3A7JmxlOyZuYnNwOzEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLDxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZDZkXHVhYzAwXHVjNzU4IFx1YzIxOCBOKDIgJmxlOyBOICZsZTsgMSAwMDApXHVhY2ZjIFx1YmU0NFx1ZDU4OVx1YWUzMFx1Yzc1OCBcdWM4ODVcdWI5NTggTSgxICZsZTsgTSAmbGU7IDEwIDAwMCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzc0XHVkNmM0IE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIGFcdWM2NDAgYiBcdWMzMGRcdWI0ZTRcdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBhXHVjNjQwIGJcdWI5N2MgXHVjNjU1XHViY2Y1XHVkNTU4XHViMjk0IFx1YmU0NFx1ZDU4OVx1YWUzMFx1YWMwMCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4mbmJzcDsoMSAmbGU7IGEsIGIgJmxlOyBuOyBhICZuZTsgYikmbmJzcDs8XC9saT5cclxuXHQ8bGk+XHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmU0NFx1ZDU4OSBcdWMyYTRcdWNmMDBcdWM5MDRcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzVmMFx1YWNiMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHVjNzc0XHViOGVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZWNcdWQ1ODlcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDBjMFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViZTQ0XHVkNTg5XHVhZTMwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzNzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGbHlpbmcgU2FmZWx5IiwiZGVzY3JpcHRpb24iOiI8cD5EdWUgdG8gYnVkZ2V0IGN1dHMsIGV2ZW4gc3BpZXMgaGF2ZSB0byB1c2UgY29tbWVyY2lhbCBhaXJsaW5lcyBub3dhZGF5cyB0byB0cmF2ZWwgYmV0d2VlbiBjaXRpZXMgaW4gdGhlIHdvcmxkLiBBbHRob3VnaCB0aGlzIG1vZGUgb2YgdHJhdmVsIGNhbiBiZSB2ZXJ5IGNvbnZlbmllbnQgZm9yIGEgc3B5LCBpdCBhbHNvIHJhaXNlcyBhIHByb2JsZW06IHRoZSBzcHkgaGFzIHRvIHRydXN0IHRoZSBwaWxvdCB0byBtYWtlIHN1cmUgaGUgaXMgbm90IGluIGRhbmdlciBkdXJpbmcgdGhlIFx1ZmIwMmlnaHQuIEFuZCBldmVuIHdvcnNlLCBzb21ldGltZXMgdGhlcmUgaXMgbm8gZGlyZWN0IFx1ZmIwMmlnaHQgYmV0d2VlbiAmbmJzcDtzb21lIHBhaXJzIG9mIGNpdGllcywgc28gdGhhdCB0aGUgc3B5IGhhcyB0byB0YWtlIG11bHRpcGxlIFx1ZmIwMmlnaHRzIHRvIGdldCB0byB0aGUgZGVzaXJlZCBsb2NhdGlvbiwgYW5kIHRodXMgaGFzIHRvIHRydXN0IG11bHRpcGxlIHBpbG90cyE8XC9wPlxyXG5cclxuPHA+VG8gbGltaXQgdGhlIHRydXN0IGlzc3VlcyB5b3UgYXJlIGFza2VkIGZvciBoZWxwLiBHaXZlbiB0aGUgXHVmYjAyaWdodCBzY2hlZHVsZSwgXHVmYjAxZ3VyZSBvdXQgdGhlIHNtYWxsZXN0IHNldCBvZiBwaWxvdHMgdGhhdCBuZWVkIHRvIGJlIHRydXN0ZWQsIHN1Y2ggdGhhdCB0aGUgc3B5IGNhbiBzYWZlbHkgdHJhdmVsIGJldHdlZW4gYWxsIGNpdGllcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIG4gKDIgJmxlOyBuICZsZTsgMSAwMDApIGFuZCBtICgxICZsZTsgbSAmbGU7IDEwIDAwMCk6IHRoZSBudW1iZXIgb2YgY2l0aWVzIGFuZCB0aGUgbnVtYmVyIG9mIHBpbG90cywgcmVzcGVjdGl2ZWx5LjxcL2xpPlxyXG5cdDxsaT5tIGxpbmVzIHdpdGggdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBhIGFuZCBiICgxICZsZTsgYSwgYiAmbGU7IG47IGEgJm5lOyBiKTogYSBwaWxvdCBcdWZiMDJ5aW5nIGhpcyBwbGFuZSBiYWNrIGFuZCBmb3J0aCBiZXR3ZWVuIGNpdHkgYSBhbmQgYi48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JdCBpcyBwb3NzaWJsZSB0byBnbyBmcm9tIGFueSBjaXR5IHRvIGFueSBvdGhlciBjaXR5IHVzaW5nIG9uZSBvciBtb3JlIFx1ZmIwMmlnaHRzLiBJbiBvdGhlciB3b3JkczogdGhlIGdyYXBoIGlzIGNvbm5lY3RlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW5kIGludGVnZXI6IHRoZSBtaW5pbXVtIG51bWJlciBvZiBwaWxvdHMgdGhhdCBuZWVkIHRvIGJlIHRydXN0ZWQgc3VjaCB0aGF0IGl0IGlzIHBvc3NpYmxlIHRvIHRyYXZlbCBiZXR3ZWVuIGVhY2ggcGFpciBvZiBjaXRpZXMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=