Connected Components :
Difficulty Level : Medium
Submissions : 456
Asked In :
Marks :100
: 11 | : 0
Given a connected tree with N vertexes from [0 to N-1] and N-1 edges. Also, you are given a vertex X that needs to be deleted from the tree. Your task is to Calculate the number of connected components in the tree if vertex X is removed from the tree.
Input
The first line of the Test contains a single integer N which is the number of nodes in the tree ($$$1 \le N \le 10^5 $$$).
The next N-1 lines contain the edges of the tree.
The last line contains a single integer X the vertex that needs to be deleted.($$$1 \le X \le N $$$)
Output
For each test case print the number of the connected components after deletion of vertex X from the tree.
Example
Input
7 0 1 0 2 0 3 1 4 1 5 3 6 0
Output
3
