You are given an undirected tree consisting of $n$ vertices. An undirected tree is a connected undirected graph with $n - 1$ edges.

Your task is to add the minimum number of edges in such a way that the length of the shortest path from the vertex $1$ to any other vertex is at most $2$. Note that you are not allowed to add loops and multiple edges.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The following $n - 1$ lines contain edges: edge $i$ is given as a pair of vertices $u_i, v_i$ ($1 \le u_i, v_i \le n$). It is guaranteed that the given edges form a tree. It is guaranteed that there are no loops and multiple edges in the given edges.


-----Output-----

Print a single integer — the minimum number of edges you have to add in order to make the shortest distance from the vertex $1$ to any other vertex at most $2$. Note that you are not allowed to add loops and multiple edges.


-----Examples-----
Input
7
1 2
2 3
2 4
4 5
4 6
5 7

Output
2

Input
7
1 2
1 3
2 4
2 5
3 6
1 7

Output
0

Input
7
1 2
2 3
3 4
3 5
3 6
3 7

Output
1



-----Note-----

The tree corresponding to the first example: [Image] The answer is $2$, some of the possible answers are the following: $[(1, 5), (1, 6)]$, $[(1, 4), (1, 7)]$, $[(1, 6), (1, 7)]$.

The tree corresponding to the second example: [Image] The answer is $0$.

The tree corresponding to the third example: [Image] The answer is $1$, only one possible way to reach it is to add the edge $(1, 3)$.
[{"code": "from sys import stdin\nn = int(stdin.readline())\ng = dict()\nfor i in range(n-1):\n    u,v = map(int,stdin.readline().split())\n    g.setdefault(u-1,[]).append(v-1)\n    g.setdefault(v-1, []).append(u-1)\nst = [0]\nrank = [0]*n\ntree = [0]*n\nmsk = [0]*n\nrd = dict()\nwhile len(st)>0:\n    top = st.pop()\n    msk[top] = 1\n    for c in g[top]:\n        if msk[c] == 0:\n            st.append(c)\n            tree[c] = top\n            rank[c] = rank[top]+1\n            rd.setdefault(rank[c], []).append(c)\nmax_rank = max(rank)\nreach = [0]*n\nbuild = [0]*n\nans = 0\nfor r in range(max_rank, 2, -1):\n    for node in rd[r]:\n        if reach[node] == 0:\n            reach[node] = 1\n            reach[tree[node]] = 1\n            reach[tree[tree[node]]] = 1\n            build[tree[node]] = 1\nprint(sum(build))", "passed": true, "time": 0.14, "memory": 14404.0, "status": "done"}, {"code": "import sys\nfrom collections import deque\nimport heapq\ninput = sys.stdin.readline\n\nN=int(input())\nEDGE=[list(map(int,input().split())) for i in range(N-1)]\n\nEDGELIST=[[] for i in range(N+1)]\n\nfor i,j in EDGE:\n    EDGELIST[i].append(j)\n    EDGELIST[j].append(i)\n\n#EDGES=[[] for i in range(N+1)]\nREDG=[None for i in range(N+1)]\nQUE=deque([1])\ncheck=[0]*(N+1)\nDEPTH=[None]*(N+1)\ni=0\nwhile QUE:\n    NQUE=deque()\n    i+=1\n    \n    while QUE:\n        x=QUE.pop()\n        DEPTH[x]=i\n        check[x]=1\n        for to in EDGELIST[x]:\n            if check[to]==1:\n                continue\n            else:\n                #EDGES[x].append(to)\n                REDG[to]=x\n                NQUE.append(to)\n    QUE=NQUE\n\n\ncheck=[0]*(N+1)\ncheck[1]=1\n#NEXT=[]\n\n#for i in EDGES[1]:\n#    check[i]=1\n#    NEXT.append(i)\n\n#for j in NEXT:\n#    for k in EDGES[j]:\n#        check[k]=1\n\n\nLEAF=[]\nfor i in range(2,N+1):\n    if len(EDGELIST[i])==1:\n        LEAF.append((-DEPTH[i],i))\n\nQUE=LEAF\nheapq.heapify(QUE)\nANS=0\n\n#print(check,QUE)\n\nwhile QUE:\n    dep,x=heapq.heappop(QUE)\n    if check[x]!=0 or dep>=-3:\n        continue\n\n    if check[REDG[x]]==2:\n        continue\n\n    if check[x]==0:\n        check[x]=1\n    if check[REDG[REDG[x]]]==0:\n        check[REDG[REDG[x]]]=1\n    check[REDG[x]]=2   \n    heapq.heappush(QUE,(-DEPTH[REDG[REDG[REDG[x]]]],REDG[REDG[REDG[x]]]))\n    ANS+=1\n\n    #print(x,QUE,check)\n\nprint(ANS)\n\n\n\n", "passed": true, "time": 0.14, "memory": 14336.0, "status": "done"}, {"code": "import sys\nfrom collections import deque\nmod = 10**9+7\nINF = float('inf')\ndef inp(): return int(sys.stdin.readline())\ndef inpl(): return list(map(int, sys.stdin.readline().split()))\n\nn = inp()\nedges = [[] for _ in range(n)]\nfor _ in range(n-1):\n    a,b = inpl()\n    a,b = a-1,b-1\n    edges[a].append(b)\n    edges[b].append(a)\ndist = [-1] * n\ndist[0] = 0\npa = [-1] * n\nse = set()\npq = []\nq = deque()\nq.append(0)\nwhile q:\n    now = q.popleft()\n    for nx in edges[now]:\n        if dist[nx] != -1:\n            continue\n        pa[nx] = now\n        dist[nx] = dist[now] + 1\n        if dist[nx] > 2:\n            se.add(nx)\n            pq.append((dist[nx], nx))\n        q.append(nx)\npq = pq[::-1]\nres = 0\nind = 0\nwhile se:\n    d,v = pq[ind]\n    ind += 1\n    if not v in se: \n        continue\n    res += 1\n    pv = pa[v]\n    se.discard(pv)\n    for nv in edges[pv]:\n        se.discard(nv)\nprint(res)", "passed": true, "time": 0.14, "memory": 14296.0, "status": "done"}, {"code": "\nimport sys\n\ndef get_new_edges(graph):\n    n = len(graph)\n    far_vertex = []\n    pi = [None]*n\n    visit = [False]*n\n    visit[0]\n    queue = [[0,0]]\n    i = 0    \n    while True:\n        if i >= len(queue): break\n        current, d = queue[i]\n        i += 1\n        visit[current] = True\n        for v in graph[current]:\n            if not visit[v]:\n                u = [v, d+1]\n                pi[v] = current\n                queue.append(u)\n                if d+1 > 2:\n                    far_vertex.append(u)\n    \n    far_vertex.sort(key=lambda x: -x[1])\n\n    pos = [None]*n\n    for i, e in enumerate(far_vertex):\n        pos[e[0]] = i\n\n    count = 0\n    for i in range(len(far_vertex)):\n        if not far_vertex[i]: continue\n        vertex, depth = far_vertex[i]\n        father = pi[vertex]\n        count += 1\n        if pos[father]:\n            far_vertex[pos[father]] = None\n        for u in graph[father]:\n            if pos[u]:\n                far_vertex[pos[u]] = None\n\n    return count\n    \ndef read_int_line():\n    return list(map(int, sys.stdin.readline().split()))\n\nvertex_count = int(input())\ngraph = [[] for _ in range(vertex_count)]\n\nfor i in range(vertex_count - 1):\n    v1, v2 = read_int_line()\n    v1 -= 1\n    v2 -= 1\n    graph[v1].append(v2)\n    graph[v2].append(v1)\n\nprint(get_new_edges(graph))\n\n\n    \n", "passed": true, "time": 0.14, "memory": 14368.0, "status": "done"}]