{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e一个网络由N台计算机组成,通过N-1个通信链接连接起来,以便任意两台计算机之间可以通过唯一路径通信。如果两台计算机之间有通信链接,则称它们是“相邻的”。计算机的“邻居”是与它相邻的计算机的集合。为了快速访问和检索大量信息,我们需要选择一些计算机作为“服务器”,为它们的邻居提供资源。注意,服务器可以为其所有邻居提供服务。网络中的一组服务器形成一个“完美的服务”,如果每个客户端(非服务器)都由“正好一个”服务器提供服务。问题是找到形成完美服务的最小服务器数量,我们称之为“完美服务数”。\u003c/p\u003e\u003cp\u003e我们假设N(≤10000)是一个正整数,这N台计算机编号从1到N。例如,图1显示了由六台计算机组成的网络,其中黑色节点表示服务器,白色节点表示客户端。在图1(a)中,服务器3和5不形成完美服务,因为客户端4与服务器3和5都相邻,因此它由两个服务器提供服务,这与假设相矛盾。相反,服务器3和4形成一个完美的服务,如图1(b)所示。该集合也具有最小的基数。因此,此示例的完美服务数等于两个。\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/d617182408b30735b731189857cbd245?v\u003d1712611522\"\u003e\u003c/div\u003e\u003cp\u003e您的任务是编写一个程序来计算完美服务数。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入包含若干测试用例。每个测试用例的格式如下:第一行包含一个正整数N,表示网络中的计算机数量。接下来的N-1行包含所有通信链接,每个链接一行。每行由两个正整数表示,用一个空格分隔。最后一行为第一个测试用例的结束符0。\u003c/p\u003e\u003cp\u003e下一个测试用例在前一个结束符0之后开始。-1表示所有输入的结束。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出包含每个测试用例的一行。每行包含一个正整数,即完美服务数。\u003c/p\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\u003e6\r\n1 3\r\n2 3\r\n3 4\r\n4 5\r\n4 6\r\n0\r\n2\r\n1 2\r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}