CF463E Caisa and Tree

Caisa is now at home and his son has a simple task for him. Given a rooted tree with $ n $ vertices, numbered from $ 1 $ to $ n $ (vertex $ 1 $ is the root). Each vertex of the tree has a value. You should answer $ q $ queries. Each query is one of the following: - Format of the query is "1 $ v $ ". Let's write out the sequence of vertices along the path from the root to vertex $ v $ : $ u_{1},u_{2},...,u_{k} $ $ (u_{1}=1; u_{k}=v) $ . You need to output such a vertex $ u_{i} $ that $ gcd(value of u_{i},value of v)>1 $ and $ i<k $ . If there are several possible vertices $ u_{i} $ pick the one with maximum value of $ i $ . If there is no such vertex output -1. - Format of the query is "2 $ v $ $ w $ ". You must change the value of vertex $ v $ to $ w $ . You are given all the queries, help Caisa to solve the problem.

N/A

N/A

$ gcd(x,y) $ is greatest common divisor of two integers $ x $ and $ y $ .