Longest Path
/

## Algorithms, Depth First Search, Depth-first search, Graph

Problem
Editorial
Analytics

You are given a tree with $N$ nodes and $N-1$ edges and an integer $K$. Each node has a label denoted by an integer, $A_i$. Your task is to find the length of the longest path such that label of all the nodes in the path are divisible by $K$.

Length of a path is the number of edges in that path.

Input Format:

First line contains two space separated integers, $N$ and $K$. Next line contains $N$ space separated integers, $i^{th}$ integer denotes the label of $i^{th}$ node, $A_i$. Next $N-1$ lines contains two space separated integers each, $U$ and $V$ denoting that there is an edge between node $U$ and node $V$.

Output Format:

Print a single integer denoting the length of the longest path such that label of all the nodes in the path are divisible by $K$.

Constraints:

$1 \le N \le 10^5$

$1 \le K \le 10^5$

$1 \le A_i \le 10^5$

$1 \le U, V \le N$

SAMPLE INPUT
6 2
4 2 3 2 3 5
1 2
1 3
2 4
2 5
3 6

SAMPLE OUTPUT
2

Explanation

Longest path will be 1->2->4.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...