{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n To prove two sets A and B are equivalent, we can first prove A is a subset of B, and then prove B is a subset of A, so finally we got that these two sets are equivalent. \n \u003cbr\u003eYou are to prove N sets are equivalent, using the method above: in each step you can prove a set X is a subset of another set Y, and there are also some sets that are already proven to be subsets of some other sets. \n \u003cbr\u003eNow you want to know the minimum steps needed to get the problem proved. \n\u003c/div\u003e\n给定一个有向图,求最少加几条边,可以使得整个图强连通。"}},{"title":"Input","value":{"format":"HTML","content":"The input file contains multiple test cases, in each case, the first line contains two integers N \u0026lt;\u003d 20000 and M \u0026lt;\u003d 50000. \n\u003cbr\u003eNext M lines, each line contains two integers X, Y, means set X in a subset of set Y.\n\u003cbr\u003e第一行两个整数,表示点数和边数。\n\u003cbr\u003e接下来m行,每行表示一条有向边。\n"}},{"title":"Output","value":{"format":"HTML","content":"For each case, output a single integer: the minimum steps needed.\n\u003cbr\u003e输出一个整数,表示最少需要添加的边。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e4 0\n3 2\n1 2\n1 3\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e4\n2\n\n \n \u003ci style\u003d\"font-size:1px\"\u003e \u003c/i\u003e\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cpre\u003eCase 2: First prove set 2 is a subset of set 1 and then prove set 3 is a subset of set 1.\n \n \u003c/pre\u003e"}}]}