Meeting in the Underground Cave

In an underground cave, the nodes are numbered from \(1\) to \(n\) and connected in a tree structure. Little hamster lives with his friend Sugar. One day, little hamster wants to go from his bedroom at node \(a\) to the dining hall at node \(b\), and at the same time, his friend will go from his bedroom at node \(c\) to the library at node \(d\). Both will travel along the unique shortest path in the tree. Determine whether it is possible for them to meet, i.e. whether the two paths have at least one node in common.

Note: All paths are unique as the cave is structured as a tree (an acyclic connected graph). Use the fact that the unique path between any two nodes in a tree can be found by a simple DFS or BFS.

If they can meet, output 1; otherwise, output 0.

inputFormat

The first line contains five integers \(n\), \(a\), \(b\), \(c\), \(d\) representing the number of nodes in the tree and the start and destination nodes for little hamster and his friend respectively.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) which denote an undirected edge between nodes \(u\) and \(v\).

outputFormat

Output a single integer: 1 if there exists at least one common node between the two shortest paths; otherwise, output 0.

sample

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

1