{"trustable":true,"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":"\u003cdiv class\u003d\"panel_content\"\u003e考虑以下练习,在一本通用的线性代数教材中找到。\u003cbr\u003e\u003cbr\u003e 设A是一个n×n矩阵。证明以下陈述是等价的:\u003cbr\u003e\u003cbr\u003e 1. A是可逆的。\u003cbr\u003e 2. 对于每个n×1矩阵b,Ax \u003d b有且仅有一个解。\u003cbr\u003e 3. 对于每个n×1矩阵b,Ax \u003d b是一致的。\u003cbr\u003e 4. Ax \u003d 0仅有平凡解x \u003d 0。\u003cbr\u003e\u003cbr\u003e解决这样的练习的典型方法是展示一系列蕴含关系。例如,可以通过展示(a)蕴含(b),(b)蕴含(c),(c)蕴含(d),最后(d)蕴含(a)。这四个蕴含关系表明这四个陈述是等价的。\u003cbr\u003e\u003cbr\u003e另一种方法是展示(a)等价于(b)(通过证明(a)蕴含(b)和(b)蕴含(a)),(b)等价于(c),以及(c)等价于(d)。然而,这种方法需要证明六个蕴含关系,显然比仅证明四个蕴含关系要多出很多工作!\u003cbr\u003e\u003cbr\u003e我已经得到了一些类似的任务,并已经开始证明一些蕴含关系。现在我想知道,我还需要证明多少个蕴含关系?你能帮我确定这个吗?\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"在第一行一个正整数:测试用例的数量,最多为100。之后每个测试用例:\u003cbr\u003e\u003cbr\u003e * 一行,包含两个整数n(1 ≤ n ≤ 20000)和m(0 ≤ m ≤ 50000):陈述的数量和已经证明的蕴含关系的数量。\u003cbr\u003e * m行,每行包含两个整数s1和s2(1 ≤ s1, s2 ≤ n且s1 ≠ s2),表示已经证明陈述s1蕴含陈述s2。"}},{"title":"输出","value":{"format":"HTML","content":"每个测试用例:\u003cbr\u003e\u003cbr\u003e * 一行,包含需要额外证明的最小蕴含关系的数量,以便证明所有陈述是等价的。"}},{"title":"示例","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\u003e2\r\n4 0\r\n3 2\r\n1 2\r\n1 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}