AlphaElectrics is currently having a problem providing electricity to the inhabitants of Alpha Planet! As a result, AlphaElectrics is redesigning its network of electrical cables. AlphaElectrics’ network of cables can be modeled as a graph of N nodes connected by N - 1 edges, where nodes represent power stations and edges represent electrical cables. Power stations are labeled from 1...N. AlphaElectrics categorizes its power stations into M different types. The ith power station has a type si.
AlphaElectrics has Q queries they want to answer, so they have asked you for help! There are two types of queries:
Help AlphaElectrics answer their queries, which will help restore power to the inhabitants of Alpha Planet!
Input Format:
Output Format:
For each query of Type 1, output a single number on a new line that represents the distance to the closest power station from power station x that is a different power station type than power station x. If there is no power station with a different power station type than power station x, output -1.
(Problem credit: Justin Li)