### PROBLEM LINK:

**Author:** Michael Nematollahi

**Tester:** Teja Vardhan Reddy

**Editorialist:** Michael Nematollahi

### PREREQUISITES:

DP

### PROBLEM:

You’re given an undirected graph with N vertices and M edges and a positive integer K. You’re also given Q constraints of the form (a_i, b_i). A walk is defined as a sequence of vertices in which every two adjacent vertices are the same or are connected by an edge. Your task is to calculate the number of walks of length K+1 that start at vertex 1 and in which for each i from 1 to Q, the (b_i+1)^{th} vertex is a_i.

### QUICK EXPLANATION:

Sort the constraints given in the input based on time. Solve the problem for each consecutive pair and multiply the results to get the answer. To solve the problem for a pair of consecutive constraints, define dp*[v] to be equal to the number of walks of length i that start at the first constraint and end at v.

### EXPLANATION:

First, check that no constraint tells you to be on a vertex other than 1 after 0 seconds. Then, check that no two constraints tell you to be on two different vertices after the same amount of time. If one of these is the case, the answer is obviously 0.

Now we’re ready to solve the problem. For the sake of simplicity, add the constraint (1, 0) to the constraints. Then, sort the constraints based on time. It’s easy to see that now we can solve the problem for every two consecutive constraints and multiply the results to get the answer to the original problem.

To solve the problem for two consecutive constraints like (a_1, b_1) and (a_2, b_2), we need to calculate the number of walks of length b_2 - b_1 that start at a_1 and end at a_2. Let’s define dp*[v] as the number of walks of length i that start at a_1 and end at v. Here’s how to calculate this dp array:

1_ The base case is dp[0][a_1] = 1.

2_ dp*[v] = \sum_{for\hspace{1mm} each\hspace{1mm} vertex\hspace{1mm} u\hspace{1mm} adjacent\hspace{1mm} to\hspace{1mm} v)} dp[i-1]

The answer for this consecutive pair would be dp[b_2 - b_1][a_2]

After finding the answer for the consecutive constraints, we need to find the number of ways we can continue our walk from the last constraint. This can easily be done using the same dp array.

The complexity of calculating the dp array for a consecutive pair of constraints is of O((b2 - b1) imes (N + M). Since the sum of (b_i - b_{i-1}) is equal to K, the total complexity of the solution is O(K imes (N+M)). To see the implementation, refer to the setter’s solution.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.