CF504E Misha and LCP on Tree

Misha has a tree with characters written on the vertices. He can choose two vertices $ s $ and $ t $ of this tree and write down characters of vertices lying on a path from $ s $ to $ t $ . We'll say that such string corresponds to pair $ (s,t) $ . Misha has $ m $ queries of type: you are given $ 4 $ vertices $ a $ , $ b $ , $ c $ , $ d $ ; you need to find the largest common prefix of the strings that correspond to pairs $ (a,b) $ and $ (c,d) $ . Your task is to help him.

The first line contains integer $ n $ ( $ 1

For each query print the length of the largest common prefix on a separate line.