{"trustable":false,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\t\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n\t MathJax.Hub.Config({\n\t extensions: [\"tex2jax.js\"],\n\t jax: [\"input/TeX\", \"output/SVG\"],\n\t tex2jax: {\n\t inlineMath: [ [\u0027$\u0027,\u0027$\u0027], [\"\\\\(\",\"\\\\)\"] ],\n\t displayMath: [ [\u0027$$\u0027,\u0027$$\u0027], [\"\\\\[\",\"\\\\]\"] ],\n\t processEscapes: true\n\t },\n\t });\n\t\u003c/script\u003e\n\t\u003cscript type\u003d\"text/javascript\"\n\t src\u003d\"https://cdn.staticfile.org/mathjax/2.7.0/MathJax.js\"\u003e\n\t\u003c/script\u003e\n \n \u003cp\u003eAlice 生活在一个人们都喜欢交朋友的国家。 朋友关系是双向的,并且 如果有两个人至少有 \u003cvar\u003ek\u003c/var\u003e 个相同的朋友, 那么他们俩过几天也会成为朋友。 目前这个国家里一共有 \u003cvar\u003en\u003c/var\u003e 个人,他们之间有\u003cvar\u003em\u003c/var\u003e对朋友 。假定任何新的朋友关系只能在他们有上述足够数量的相同朋友的情况下产生, 现在需要你计算在足够长的时间后一共有多少新的朋友关系产生\u003c/p\u003e \n \u003cp\u003e\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003e第一行输入一个 \u003cvar\u003eT\u003c/var\u003e (约为 100) 表示测试数据的组数。 接下来 \u003cvar\u003eT\u003c/var\u003e 组数据。对每组数据, 第一行包含3个数 \u003cvar\u003en, m, k\u003c/var\u003e (1 ≤ \u003cvar\u003en\u003c/var\u003e ≤ 100, 0 ≤ \u003cvar\u003em\u003c/var\u003e ≤ \u003cvar\u003en×(n-1)/2\u003c/var\u003e, 0 ≤ \u003cvar\u003ek\u003c/var\u003e ≤ \u003cvar\u003en\u003c/var\u003e,不存在重复的朋友关系) 下面的 \u003cvar\u003em\u003c/var\u003e 行表示当前朋友关系. 第 \u003cvar\u003ei\u003c/var\u003e 个朋友关系 包含两个整数 \u003cvar\u003eu\u003csub\u003ei\u003c/sub\u003e,,v\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (0 ≤ \u003cvar\u003eu\u003csub\u003ei\u003c/sub\u003e, v\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u0026lt; \u003cvar\u003en\u003c/var\u003e, \u003cvar\u003eu\u003csub\u003ei\u003c/sub\u003e ≠ v\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e) 表示\u003cvar\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e 和 \u003cvar\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e是朋友.\u003c/p\u003e \n \u003cp\u003e\u003cstrong\u003e注释: 测试数据中的朋友关系为随机生成。\u003c/strong\u003e\u003c/p\u003e \n \u003ch4"}},{"title":"Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003e对每组测试数据,在一行中输出答案\u003c/p\u003e \n \u003ch4"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003e\u003c/p\u003e\n \u003cpre\u003e3\n4 4 2\n0 1\n0 2\n1 3\n2 3\n5 5 2\n0 1\n1 2\n2 3\n3 4\n4 0\n5 6 2\n0 1\n1 2\n2 3\n3 4\n4 0\n2 0\u003c/pre\u003e\n \u003cp\u003e\u003c/p\u003e \n \u003ch4"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003e\u003c/p\u003e\n \u003cpre\u003e2\n0\n4\u003c/pre\u003e\n \u003cp\u003e\u003c/p\u003e \n "}}]}