Hello coders, today we are going to solve** Chef and Pairs CodeChef Solution** whose Problem Code is **PAIRCNT**.

**Task**

You are given a tree (connected, undirected, acyclic graph) consisting of * N* nodes. Based on this tree, you have to answer

*queries.*

**Q**Each query is of the form:

– output the number of*K D V*_{1}V_{2}. . . V_{K}**pairs (**such that the shortest path between nodes*i*,*j*), 1 ≤*i*<*j*≤*K*,and*V*_{i}in the tree has**V**_{j }edges.*D*

**Input**

- The first line contains an integer
, the number of test cases. Then the test cases follow.**T** - The first line of each test case contains two integers,
and**N**.**Q** lines follow. Each line consists of two integers*N*− 1and**u**, indicating that there is an edge between nodes**v**and**u**in the tree.**v**lines follow. Each line describes a query in the format given above.**Q**

**Output**

For each query, output the answer on a new line.

**Constraints**

**1 ≤ T ≤ 5****1 ≤***N*,*Q*≤ 10^{5}**1 ≤***u*,*v*,*V*_{i}≤*N***0 ≤***D*≤ 10^{5}- The sum of
across all queries in a single test case is at most**K****10**.^{5}

**Subtasks**

**Subtask 1 (20 points):** For each query, *K* ≤ 10**Subtask 2 (80 points)**: Original constraints

**Sample Input**

```
1
5 2
1 2
1 3
2 4
4 5
3 2 2 3 5
2 4 1 3
```

**Sample Output**

```
2
0
```

**Explanation**

In the first query, the pairs of nodes **(2, 3)** and **(2, 5)** have distance **2**.

In the second query, there is no pair with distance **4**.

**Solution – Chef and Pairs**

**C++**

**Python**

**Java**

**Disclaimer: **The above Problem **(Chef and Pairs) **is generated by **CodeChef** but the Solution is Provided by **CodingBroz**. This tutorial is only for** Educational** and **Learning** Purpose.