It is well known that with link cut tree you can perform operations such as path updates, path queries, add or delete edge, check connectivity on dynamic tree/forest online.

To find if \(\exist z\) adjacent to both \(u\) and \(v\), we store two value on each node \((+, \oplus)\), and initialize each node with \((1, i)\). If the sum of path query of \((u, v)\) is \(3\), we can find \(z\) by taking \(\oplus\) with \(u\) and \(v\) to find \(z\).

Time complexity: \(O(n \log n)\)

Submission 107ms