CF506D Mr. Kitayuta's Colorful Graph

Mr. Kitayuta has just bought an undirected graph with $ n $ vertices and $ m $ edges. The vertices of the graph are numbered from 1 to $ n $ . Each edge, namely edge $ i $ , has a color $ c_{i} $ , connecting vertex $ a_{i} $ and $ b_{i} $ . Mr. Kitayuta wants you to process the following $ q $ queries. In the $ i $ -th query, he gives you two integers - $ u_{i} $ and $ v_{i} $ . Find the number of the colors that satisfy the following condition: the edges of that color connect vertex $ u_{i} $ and vertex $ v_{i} $ directly or indirectly.

N/A

N/A

Let's consider the first sample.  The figure above shows the first sample. - Vertex $ 1 $ and vertex $ 2 $ are connected by color $ 1 $ and $ 2 $ . - Vertex $ 3 $ and vertex $ 4 $ are connected by color $ 3 $ . - Vertex $ 1 $ and vertex $ 4 $ are not connected by any single color.