{"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":"期末考结束了,cfk本以为可以安心享受寒假了。结果老师给他安排了一项特别难的作业:ac自动机fail树上dfs序建可持久化线段树。\n\u003cbr\u003e因为这实在是太难了,cfk怎么做都做不出来。但是好在cfk人缘好,他决定从他的朋友里面挑一些人帮他完成这项作业。cfk共有1e7个朋友。\n前面已经说过,cfk的朋友和cfk一样挑剔,他们只愿意和自己的朋友一起合作帮助cfk。\n\u003cbr\u003e最初,这1e7个人在一个房间里,cfk可以让一些人离开房间,使得最终这个房间剩下的人都互为朋友(直接或间接的都可以,即a和b是朋友,b和c是朋友,那么房间里最后可以剩下a,b,c),\n给定n个直接的朋友关系,求cfk最多能找到多少人帮他完成作业,即最后房间里最多能剩下多少人。\n\n\n\u003cbr\u003e简单地说,给定n个直接的朋友关系,求一个最大的集合,使这个集合里的所有人都直接或间接的满足朋友关系,求这个集合的大小。"}},{"title":"Input","value":{"format":"HTML","content":"(多组输入) 输入n (0 ≤ n ≤ 100 000) - 直接的朋友关系. 接下来n行,每行输入两个数A,B,A与B互为朋友(A ≠ B, 1 ≤ A, B ≤ 10000000)"}},{"title":"Output","value":{"format":"HTML","content":"cfk最多能找到多少人,即集合大小的最大值\n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e4\n1 2\n3 4\n5 6\n1 6\n4\n1 2\n3 4\n5 6\n7 8\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e4\n2\n\n\n \n \u003ci style\u003d\"font-size:1px\"\u003e \u003c/i\u003e\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cpre\u003e\nA and B are friends(direct or indirect), B and C are friends(direct or indirect), \nthen A and C are also friends(indirect).\n\n In the first sample {1,2,5,6} is the result.\nIn the second sample {1,2},{3,4},{5,6},{7,8} are four kinds of answers.\n \n \n \u003c/pre\u003e"}}]}