시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 5299 3189 2461 62.257%

문제

상근이는 겨울방학을 맞아 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+XHVjNzc0XHViYzg4IFx1YmMyOVx1ZDU1OSBcdWIzZDlcdWM1NDhcdWM3NTggXHViZTQ0XHVkNTg5IFx1YzJhNFx1Y2YwMFx1YzkwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgPHN0cm9uZz5cdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1Yzg4NVx1Yjk1ODxcL3N0cm9uZz5cdWM3NTggXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1ZDBjMFx1YWNlMCBcdWJhYThcdWI0ZTAgXHVhZDZkXHVhYzAwXHViNGU0XHVjNzQ0Jm5ic3A7XHVjNWVjXHVkNTg5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAmbmJzcDtcdWQ1NWMgXHVhZDZkXHVhYzAwXHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWFkNmRcdWFjMDBcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0YyBcdWIyZTRcdWI5NzggXHVhZDZkXHVhYzAwXHViOTdjIFx1YWM3MFx1Y2NkMCBcdWFjMDBcdWIzYzQoXHVjMmVjXHVjOWMwXHVjNWI0IFx1Yzc3NFx1YmJmOCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHVhZDZkXHVhYzAwXHViNzdjXHViM2M0KSBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUKFQmbmJzcDsmbGU7Jm5ic3A7MTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkNmRcdWFjMDBcdWM3NTggXHVjMjE4IE4oMiAmbGU7IE4gJmxlOyAxIDAwMClcdWFjZmMgXHViZTQ0XHVkNTg5XHVhZTMwXHVjNzU4IFx1Yzg4NVx1Yjk1OCBNKDEgJmxlOyBNICZsZTsgMTAgMDAwKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWQ2YzQgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgYVx1YzY0MCBiIFx1YzMwZFx1YjRlNFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIGFcdWM2NDAgYlx1Yjk3YyBcdWM2NTVcdWJjZjVcdWQ1NThcdWIyOTQgXHViZTQ0XHVkNTg5XHVhZTMwXHVhYzAwIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiZuYnNwOygxICZsZTsgYSwgYiAmbGU7IG47IGEgJm5lOyBiKSZuYnNwOzxcL2xpPlxyXG5cdDxsaT5cdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViZTQ0XHVkNTg5IFx1YzJhNFx1Y2YwMFx1YzkwNFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjNWYwXHVhY2IwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWM3NzRcdWI4ZWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWJhYThcdWI0ZTAgXHVhZDZkXHVhYzAwXHViOTdjIFx1YzVlY1x1ZDU4OVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkMGMwXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWJlNDRcdWQ1ODlcdWFlMzAgXHVjODg1XHViOTU4XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTM3MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZseWluZyBTYWZlbHkiLCJkZXNjcmlwdGlvbiI6IjxwPkR1ZSB0byBidWRnZXQgY3V0cywgZXZlbiBzcGllcyBoYXZlIHRvIHVzZSBjb21tZXJjaWFsIGFpcmxpbmVzIG5vd2FkYXlzIHRvIHRyYXZlbCBiZXR3ZWVuIGNpdGllcyBpbiB0aGUgd29ybGQuIEFsdGhvdWdoIHRoaXMgbW9kZSBvZiB0cmF2ZWwgY2FuIGJlIHZlcnkgY29udmVuaWVudCBmb3IgYSBzcHksIGl0IGFsc28gcmFpc2VzIGEgcHJvYmxlbTogdGhlIHNweSBoYXMgdG8gdHJ1c3QgdGhlIHBpbG90IHRvIG1ha2Ugc3VyZSBoZSBpcyBub3QgaW4gZGFuZ2VyIGR1cmluZyB0aGUgXHVmYjAyaWdodC4gQW5kIGV2ZW4gd29yc2UsIHNvbWV0aW1lcyB0aGVyZSBpcyBubyBkaXJlY3QgXHVmYjAyaWdodCBiZXR3ZWVuICZuYnNwO3NvbWUgcGFpcnMgb2YgY2l0aWVzLCBzbyB0aGF0IHRoZSBzcHkgaGFzIHRvIHRha2UgbXVsdGlwbGUgXHVmYjAyaWdodHMgdG8gZ2V0IHRvIHRoZSBkZXNpcmVkIGxvY2F0aW9uLCBhbmQgdGh1cyBoYXMgdG8gdHJ1c3QgbXVsdGlwbGUgcGlsb3RzITxcL3A+XHJcblxyXG48cD5UbyBsaW1pdCB0aGUgdHJ1c3QgaXNzdWVzIHlvdSBhcmUgYXNrZWQgZm9yIGhlbHAuIEdpdmVuIHRoZSBcdWZiMDJpZ2h0IHNjaGVkdWxlLCBcdWZiMDFndXJlIG91dCB0aGUgc21hbGxlc3Qgc2V0IG9mIHBpbG90cyB0aGF0IG5lZWQgdG8gYmUgdHJ1c3RlZCwgc3VjaCB0aGF0IHRoZSBzcHkgY2FuIHNhZmVseSB0cmF2ZWwgYmV0d2VlbiBhbGwgY2l0aWVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgbiAoMiAmbGU7IG4gJmxlOyAxIDAwMCkgYW5kIG0gKDEgJmxlOyBtICZsZTsgMTAgMDAwKTogdGhlIG51bWJlciBvZiBjaXRpZXMgYW5kIHRoZSBudW1iZXIgb2YgcGlsb3RzLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcblx0PGxpPm0gbGluZXMgd2l0aCB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGEgYW5kIGIgKDEgJmxlOyBhLCBiICZsZTsgbjsgYSAmbmU7IGIpOiBhIHBpbG90IFx1ZmIwMnlpbmcgaGlzIHBsYW5lIGJhY2sgYW5kIGZvcnRoIGJldHdlZW4gY2l0eSBhIGFuZCBiLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkl0IGlzIHBvc3NpYmxlIHRvIGdvIGZyb20gYW55IGNpdHkgdG8gYW55IG90aGVyIGNpdHkgdXNpbmcgb25lIG9yIG1vcmUgXHVmYjAyaWdodHMuIEluIG90aGVyIHdvcmRzOiB0aGUgZ3JhcGggaXMgY29ubmVjdGVkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbmQgaW50ZWdlcjogdGhlIG1pbmltdW0gbnVtYmVyIG9mIHBpbG90cyB0aGF0IG5lZWQgdG8gYmUgdHJ1c3RlZCBzdWNoIHRoYXQgaXQgaXMgcG9zc2libGUgdG8gdHJhdmVsIGJldHdlZW4gZWFjaCBwYWlyIG9mIGNpdGllcy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==