Server Time: Sun Jan 21, 2018 11:58 pm
Welcome ( logout
1406 - Assassin`s Creed
  PDF (English) Statistics Forum
Time Limit: 4 second(s) Memory Limit: 32 MB

Altair is in great danger as he broke the three tenets of the assassin creed. The three tenets are: 1) never kill an innocent people, 2) always be discrete and 3) never compromise the brotherhood. As a result Altair is given another chance to prove that he is still a true assassin. Altair has to kill n targets located in n different cities. Now as time is short, Altair can send a massage along with the map to the assassin's bureau to send some assassins who will start visiting cities and killing the targets. An assassin can start from any city, but he cannot visit a city which is already visited by any other assassin except him (because they do not like each other's work). He can visit a city multiple times though. Now Altair wants to find the minimum number of assassins needed to kill all the targets. That's why he is seeking your help.


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

Each case starts with a blank line. Next line contains two integers n (1 ≤ n ≤ 15) and m (0 ≤ m ≤ 50), where n denotes the number of cities and m denotes the number of one way roads. Each of the next m lines contains two integers u v (1 ≤ u, v ≤ n, u ≠ v) meaning that there is a road from u to v. Assume that there can be at most one road from a city u to v.


For each case, print the case number and the minimum number of assassins needed to kill all the targets.

Sample Input

Output for Sample Input



3 2

1 2

2 3


6 6

1 2

2 3

2 4

5 4

4 6

4 2

Case 1: 1

Case 2: 2


Problem Setter: Muhammad Rifayat Samee
Special Thanks: S. M. Ijaz-ul-Amin Chowdhury, Jane Alam Jan, Momontho Mashak Monmoy
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan