{"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在这些假设条件下,你的任务是编写一个程序,找出可以降落在城镇并访问所有十字路口的最少伞兵数量,使得没有一个十字路口被多于一个伞兵访问。每个伞兵降落在一个十字路口,并可以沿着城镇的街道访问其他十字路口。每个伞兵的起始十字路口没有限制。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"你的程序应该读取一组组数据。输入文件的第一行包含数据组的数量。每组数据指定了城镇的结构,格式如下:\u003cbr\u003e\u003cbr\u003e十字路口数量\u003cbr\u003e街道数量\u003cbr\u003eS1 E1\u003cbr\u003eS2 E2\u003cbr\u003e......\u003cbr\u003eS街道数量 E街道数量\u003cbr\u003e\u003cbr\u003e每组数据的第一行包含一个正整数十字路口数量(大于0且小于等于120),即城镇中十字路口的数量。第二行包含一个正整数街道数量,即城镇中的街道数量。接下来的街道数量行,每行代表城镇中的一条街道,随机排序,表示城镇的街道。与第k条街道对应的行(k \u003c\u003d 街道数量)由两个正整数组成,用一个空格分隔:Sk(1 \u003c\u003d Sk \u003c\u003d 十字路口数量)- 表示街道起点的十字路口编号,Ek(1 \u003c\u003d Ek \u003c\u003d 十字路口数量)- 表示街道终点的十字路口编号。十字路口用从1到十字路口数量的整数表示。\u003cbr\u003e\u003cbr\u003e相邻数据组之间没有空行。输入数据是正确的。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"程序的输出结果是标准输出。对于每组输入数据,程序在一行上打印一个整数,即访问城镇所有十字路口所需的最少伞兵数量。\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\r\n3\r\n3 4\r\n1 3\r\n2 3\r\n3\r\n3\r\n1 3\r\n1 2\r\n2 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}