八、傳染病控制 【問題背景】 近來，一種新的傳染病肆虐全球。蓬萊國也發(fā)現(xiàn)了零星感染者，為防止該病在蓬萊國大范圍流行，該國政府決定不惜一切代價(jià)控制傳染病的蔓延。不幸的是，由于人們尚未完全認(rèn)識(shí)這種傳染病，難以準(zhǔn)確判別病毒攜帶者，更沒有研制出疫苗以保護(hù)易感人群。于是，蓬萊國的疾病控制中心決定采取切斷傳播途徑的方法控制疾病傳播。經(jīng)過 WHO（世界衛(wèi)生組織）以及全球各國科研部門的努力，這種新興傳染病的傳播途徑和控制方法已經(jīng)研究消楚，剩下的任務(wù)就是由你協(xié)助蓬萊國疾控中心制定一個(gè)有效的控制辦法。 【問題描述】 研究表明，這種傳染病的傳播具有兩種很特殊的性質(zhì)； 第一是它的傳播途徑是樹型的，一個(gè)人X只可能被某個(gè)特定的人Y感染，只要Y不得病，或者是XY之間的傳播途徑被切斷，則X就不會(huì)得病。 第二是，這種疾病的傳播有周期性，在一個(gè)疾病傳播周期之內(nèi)，傳染病將只會(huì)感染一代患者，而不會(huì)再傳播給下一代。 這些性質(zhì)大大減輕了蓬萊國疾病防控的壓力，并且他們已經(jīng)得到了國內(nèi)部分易感人群的潛在傳播途徑圖（一棵樹）。但是，麻煩還沒有結(jié)束。由于蓬萊國疾控中心人手不夠，同時(shí)也缺乏強(qiáng)大的技術(shù)，以致他們?cè)谝粋€(gè)疾病傳播周期內(nèi)，只能設(shè)法切斷一條傳播途徑，而沒有被控制的傳播途徑就會(huì)引起更多的易感人群被感染（也就是與當(dāng)前已經(jīng)被感染的人有傳播途徑相連，且連接途徑?jīng)]有被切斷的人群）。當(dāng)不可能有健康人被感染時(shí)，疾病就中止傳播。所以，蓬萊國疾控中心要制定出一個(gè)切斷傳播途徑的順序，以使盡量少的人被感染。你的程序要針對(duì)給定的樹，找出合適的切斷順序?！据斎敫袷健? 輸入格式的第一行是兩個(gè)整數(shù)n（1≤n≤300）和p。接下來p行，每一行有兩個(gè)整數(shù)i和j，表示節(jié)點(diǎn)i和j間有邊相連（意即，第i人和第j人之間有傳播途徑相連）。其中節(jié)點(diǎn)1是已經(jīng)被感染的患者?！据敵龈袷健? 只有一行，輸出總共被感染的人數(shù)?！据斎霕永?7 6 1 2 1 3 2 4 2 5 3 6 3 7【輸出樣例】 3