Lowest Common Ancestor in a Network

You are given a network of computers structured as a tree. Each computer has a unique ID from 1 to n, and the relationships between computers are given as a set of directed edges (parent to child). Given two computers, u and v, your task is to find their Lowest Common Ancestor (LCA) – that is, the deepest node (closest to u and v) which is an ancestor of both.

The problem guarantees that the network is a valid tree, meaning that every computer (except the root) has exactly one parent. The LCA of a node with itself is the node itself.

Note: All formulas in this problem use LaTeX formatting. For example, the LCA of nodes \(u\) and \(v\) is defined as the node \(w\) such that \(w \in Ancestors(u) \cap Ancestors(v)\) and for every other node \(w' \in Ancestors(u) \cap Ancestors(v)\), the depth of \(w'\) is not greater than that of \(w\).

inputFormat

The input is read from STDIN. The first line contains an integer (n), the number of computers. The second line contains an integer (m), the number of edges. Each of the next (m) lines contains two space-separated integers (p) and (c), indicating an edge from parent (p) to child (c). The last line contains two integers (u) and (v) separated by a space, representing the two computers for which you are to find the LCA.

outputFormat

Output to STDOUT a single integer representing the lowest common ancestor of computers (u) and (v).## sample

7
6
1 2
1 3
3 4
3 5
4 6
4 7
6 7

4