The number of ways to reach city $$$N$$$ in $$$D$$$ days can be basically written as a linear recurrence, with its transition matrix being same as adjacency matrix for positions not on main diagonal elements and $$$L_i$$$ for position $$$(i, i)$$$ in matrix. We can use matrix exponentiation to solve in $$$O(N^3+Q*N^2*log(D)$$$ by precomputing powers of transition matrix.

One way is to use Berlekamp-Massey Algorithm along with FFT as mentioned here but this might have too high constant factor, so do as the setter says. The best setter notes i ever saw. Thanks to @pieguy

Jordan decomposition solution (Setter's solution) Since Chef only moves from lower numbered cities to higher numbered cities, the adjacency matrix is triangular. It follows that the eigenvalues (let's call them E_i) are the values on the diagonal, and therefore a Jordan decomposition exists.

Denote m_i to be the multiplicity of a given eigenvalue — 0 for the first occurrence, 1 for the next, and so on. The existence of a Jordan decomposition implies constants $$$C_{j,i}$$$ exist such that the number of ways to reach city j in D days is given by $$$\sum_{i = 1}^N((^DC_{m_i})E_i^{D-m_i} * C_{j,i})$$$. We only need to compute these constants. Complexity: $$$O(N * M + N * Q * log(MAXD))$$$

For 30 points, the max independent set of L(G) is the size of maximum matching in general graph, which can be found via Edmond Karp/Blossom algorithm.

For full solution, solve for each connected component independently. So $$$k \leq 6$$$ and we need to find the max matching. Let's simulate and find the first line graph, calling it $$$H$$$. Now the Number of nodes in graph is up to $$$M$$$ and number of edges up to $$$M^2$$$. $$$k \leq 5$$$ on graph $$$H$$$ would work.

Fact: The size of maximum matching in line graph is just the number of vertices in L(G)/2, which is same as the number of edges/2 in $$$G$$$. So, we need to find the number of vertices in $$$L^5(H)$$$ which is same as number of edges in $$$L^4(H)$$$

We can use the fact that number of edges in a graph is $$$\sum d_i(d_i-1)/2$$$ and casework to solve the rest.