{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003eI was given the task to make all the major two way roads in Bangladesh into one way roads. And I have done that easily with some great pruning. And I asked the \u003cspan\u003eGovt\u003c/span\u003e. Traffic Management System to change the direction of all the roads.\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eBut after some days, I realized that I should have thought of the fact that all cities should be reachable from other cities using the existing one way roads. Since the traffic system is already designed, so it may not be changed. But I can ask the \u003cspan\u003egovt\u003c/span\u003e. to build new roads between any pair of cities.\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eNow since the task looks quite hard for me, I am asking you to do it for me. I will give you the current roads configuration. You have to find the minimum number of roads that have to be built such that it\u0027s possible to go from any city to any other city.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003eInput starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e≤ 25)\u003c/b\u003e, denoting the number of test cases.\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eEach case starts with a blank line. Next line contains two integers \u003cb\u003en (1 ≤ n ≤ 20000)\u003c/b\u003e and \u003cb\u003em (0 ≤ m ≤ 50000)\u003c/b\u003e, where \u003cb\u003en\u003c/b\u003e denotes the number of cities and \u003cb\u003em\u003c/b\u003e denotes the number of one way roads. Each of the next \u003cb\u003em\u003c/b\u003e lines contains two integers \u003cb\u003eu v (1 ≤ u, v ≤ n, u ≠ v)\u003c/b\u003e meaning that there is a road from \u003cb\u003eu\u003c/b\u003e to \u003cb\u003ev\u003c/b\u003e. Assume that there can be at most one road from a city \u003cb\u003eu\u003c/b\u003e to \u003cb\u003ev\u003c/b\u003e.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003eFor each case, print the case number and the minimum number of roads that have to be built.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e3 0\u0026nbsp;\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e3 2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e1 2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e1 3\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003eCase 1: 3\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eCase 2: 2\u003c/span\u003e\u003c/p\u003e"}}]}