## A Tree Problem

View as PDF

Points: 7
Time limit: 1.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.