A Tree Problem

View as PDF

Submit solution


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.


Comments

There are no comments at the moment.