题目内容

消防员正在给城市铺设消防栓，城市的道路可以看作一个连通且无回路的图，每条道路有两个底座，消防栓必须铺设在底座上，每条道路必须有消防栓盖；交叉路口只有一个消防栓底座；交叉路口的消防栓可以覆盖连接的所有道路，求至少需要多少个消防栓才能覆盖城市所有的道路?

输入描述

每个 $case$ ，第一行一个整数 $n$ ，表示底座数。($1<=n<=1500$)