Bob 喜歡玩電腦游戲，特別是戰(zhàn)略游戲。但是他經(jīng)常無(wú)法找到快速玩過(guò)游戲的方法?，F(xiàn)在他有個(gè)問(wèn)題。

現(xiàn)在他有座古城堡，古城堡的路形成一棵樹(shù)。他要在這棵樹(shù)的節(jié)點(diǎn)上放置最少數(shù)目的士兵，使得這些士兵能夠瞭望到所有的路。

注意：某個(gè)士兵在一個(gè)節(jié)點(diǎn)上時(shí)，與該節(jié)點(diǎn)相連的所有邊都將能被瞭望到。

請(qǐng)你編一個(gè)程序，給定一棵樹(shù)，幫 Bob 計(jì)算出他最少要放置的士兵數(shù)。

輸入數(shù)據(jù)表示一棵樹(shù)，描述如下。

第一行一個(gè)數(shù) N ，表示樹(shù)中節(jié)點(diǎn)的數(shù)目。

第二到第 N+1 行，每行描述每個(gè)節(jié)點(diǎn)信息，依次為該節(jié)點(diǎn)編號(hào) i，數(shù)值 k，k 表示后面有 k 條邊與節(jié)點(diǎn) i 相連，接下來(lái) k 個(gè)數(shù)，分別是每條邊的所連節(jié)點(diǎn)編號(hào) r₁,r₂,?,r_k 。

對(duì)于一個(gè)有 N 個(gè)節(jié)點(diǎn)的樹(shù)，節(jié)點(diǎn)標(biāo)號(hào)在 0 到 N?1 之間，且在輸入文件中每條邊僅出現(xiàn)一次。

數(shù)據(jù)范圍與提示：

對(duì)于 100% 的數(shù)據(jù)，有 0<N≤1500。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃