Server Time: Wed Sep 23, 2020 7:25 am
Welcome ( logout
I - A Perfect Murder
  PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

"Yes, I am the murderer. No doubt" I had to confess it in front of all. But wait, why I am confessing? Nobody wants to go to jail, neither do I. As you have suspected there is something fishy. So, let me explain a bit.

The murder was happened in 19th June, at 11:30 pm this year (2009) according to the medical report. So, I was asking the judge "Can you find the time 19th June 11:30 pm in Bangladesh?" The judge informed other reporters to find the time. But alas! There was no time - "2009, 19th June, 11:30 pm". So, the judge got a bit confused about my confession. So, I began to tell them, "The time the murder was happened, is not a valid time according to you. So, how can you claim that I am the murderer?"

And what happened next, you all know. I am in the streets again with a clean sheet.

But now I have planned to kill again. I have a list of N mosquitoes which are to be killed. But there is a small problem. If I kill a mosquito, all of his friends will be informed, so they will be prepared for my attack, thus they will be impossible to kill. But there is a surprising fact. That is if I denote them as a node and their friendship relations as edges, the graph becomes acyclic.

Now I am planning when and how to kill them (how to get rid of the law!) and you have to write a program that will help me to find the maximum number of mosquito I can kill. Don't worry too much, if anything goes wrong I will not mention your name, trust me!


Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a blank line and two integers N (1 ≤ N ≤ 1000) denoting the number of mosquito I want to kill and M denoting the number of friendship configurations. Each of the next M lines contains two integers a and b denoting that ath and bth mosquitoes are friends. You can assume that (1 ≤ a, b ≤ N, a ≠ b) and each friendship relation is given only once. As I have already mentioned, you will not find any cycle in the relations.


For each case, print the case number and the maximum number of mosquitoes I can kill considering the conditions described above.

Sample Input

Output for Sample Input



4 3

1 2

1 3

1 4


3 2

1 2

2 3


5 4

1 2

1 3

2 4

2 5

Case 1: 3

Case 2: 2

Case 3: 3


Problem Setter: Jane Alam Jan
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan