A Tree Problem

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Java 8 2.0s
Memory limit: 64M

Author:
Problem type

Given a tree of N nodes, and two paths, one from a to b and another from c to d, find the number of nodes that are part of both paths.

Input Specification

The first line will contain the integer N (1 \le N \le 10^5).

The second line will contain four integers, a, b, c, d (1 \le a, b, c, d \le N).

The next N-1 lines will each contain two integers, u, v (1 \le u, v \le N).

It is guaranteed the entire tree is connected.

Output Specification

Output the number of nodes that are part of both paths.

Sample Input

5
1 5 2 4
1 3
2 4
3 4
5 4

Sample Output

1

Explanation for Sample

Only node 4 is part of both paths.


Comments

There are no comments at the moment.