{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"![Image Text](CDN_BASE_URL/6b4cfcea292e1fbbb98e0d91e605c3dc?v\u003d1715625734)\n\nEzio needs to kill **N** targets located in **N** different cities. The cities are connected by some one way roads. As time is short, Ezio can send a massage along with the map to the assassin\u0027s bureau to send some assassins who will start visiting cities and killing the targets. An assassin can start from any city, he/she may visit any city multiple times even if the cities that are already visited by other assassins.\n\nEzio wants to find the minimum number of assassins needed to do the job."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 70)**, denoting the number of test cases.\n\nEach case starts with a blank line. Next line contains two integers **N (1 \u0026#8804; N \u0026#8804; 1000)** and **M(0 \u0026#8804; M \u0026#8804; 10000)**, where **N** denotes the number of cities and **M** denotes the number of one way roads.\n\nEach of the next **M** lines contains two integers **u v (1 \u0026#8804; u, v\u0026#8804; N, u \u0026#8800; 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**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the minimum number of assassins needed to kill all targets."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\n5 4\n1 2\n1 3\n4 1\n5 1\n\n7 0\n\n8 8\n1 2\n2 3\n3 4\n4 1\n1 6\n6 7\n7 8\n8 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2\nCase 2: 7\nCase 3: 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"Dataset is huge, use faster I/O methods."}}]}