A new land, what we call “chor”, has emerged. Local people have already given it a name “Chor Tintin Tikri” and taken hold of some part of the land. You are among one of the powerful people so you got a big portion of land for yourself. Now you decided to divide the land into parts and let the local farmers cultivate it.
You are a big fan of Pizza Ghat, and pizza is your favorite food. You even dream about pizza. So you have made a decision to divide your newly acquired land in triangular shapes. You have already told your people to start dividing the land. They have started to make each part in triangular shape and put a pole on three corners of each part. But to do this they require a lot of time.
After hearing your decision, the farmers have demanded that their land should have different color of poles on each corner. Now after you told the workers who are dividing the land to color each pole, they quit and left you with some part properly divided and others not so much.
In the meantime, cultivating season has started and you will face a huge loss if you don’t give distribute the land among the farmers for cultivation. So you decided to color the every pole which is already set according to the farmers demand. (You will also color those poles which doesn’t make a triangle yet, so you may cheat them later by not coloring the next poles which will be set. As after those are set, the coloring scheme may be invalid. Any how, you don’t need to think about this too hard!!)
As you want to save money you have decided to buy minimum types of color by which you can color all the poles which are already set according to the farmers demand. Your job now is to determine this minimum value.
Input starts with number of testcases, T (1 ≤ T ≤ 100). Each case starts with two integers, V (1 ≤ V ≤ 1000) and E (1 ≤ E ≤ 5000) , where V is the number of poles (or nodes) and E is the number of division lines (or edges). Then E lines follow, each line containing X and Y (1 ≤ X, Y ≤ V) denoting a division line between X pole and Y pole.
Minimum type of color you have to buy.
| Input | Output |
|---|---|
2 2 1 1 2 5 7 1 2 2 3 1 3 3 4 2 4 2 5 4 5 | Case 1: 2 Case 2: 3 |