Edge Removal to Disconnect Special Pairs in a Tree

Given a tree with n nodes and m unordered pairs \( (a_i, b_i) \) where all \(a_i\) are distinct, all \(b_i\) are distinct, and \(a_i \neq b_j\) for all \(1 \le i,j \le m\), determine if it is possible to remove exactly one edge from the tree such that for every pair \( (a_i, b_i) \) the two nodes become disconnected.

If such an edge exists, output its index (edges are numbered from 1 in the input order); otherwise, output \(-1\).

inputFormat

The first line contains two integers \(n\) and \(m\) where \(n\) is the number of nodes and \(m\) is the number of special pairs. The next \(n-1\) lines each contain two integers \(u\) and \(v\) representing an edge between nodes \(u\) and \(v\). The following \(m\) lines each contain two integers \(a_i\) and \(b_i\) representing a special pair.

outputFormat

Output a single integer: the index of an edge that, when removed, disconnects every special pair \( (a_i, b_i) \) (i.e. each \(a_i\) and \(b_i\) lie in different components). If no such edge exists, output \(-1\).

sample

3 1
1 2
2 3
1 3

1