Complete the implementation of the function k$\_$tsp$\_$mtz$\_$encoding$($n$,$ k$,$ cost$\_$matrix$)$ below using PULP. It follows the same input convention as the code supplied in the notes. The input n denotes the size of the graph with vertices labeled $0,..,$ n$-1,$ k is the number of salespeople, and cost$\_$matrix is a list of lists wherein cost$\_$matrix$[$i$][$j$]$ is the edge cost to go from i to j for i $!=$ j$.$ Your code must avoid accessing cost$\_$matrix$[$i$][$i$]$ to avoid bugs. These entries will be supplied as None in the test cases.

Your code must return a list lst that has exactly k

lists in it$,$ wherein lst$[$j$]$ represents the locations visited by the jth

salesperson.

For the example above, for k$=2$

$,$ your code must return

$[[0,2,1,4],[0,3]]$

For the example above, for k$=3$

$,$ your code must return

$[[0,1,4],[0,2],[0,3]]$from pulp import $*$

def k$\_$tsp$\_$mtz$\_$encoding$($n$,$ k$,$ cost$\_$matrix$)$:

# check inputs are OK

assert $1<=$ k $<$ n

assert len$($cost$\_$matrix$)==$ n$,$ f'Cost matrix is not $\{$n$\}$x$\{$n$\}\text{'}$

assert all$($len$($cj$)==$ n for cj in cost$\_$matrix$),$ f'Cost matrix is not $\{$n$\}$x$\{$n$\}\text{'}$

prob $=$ LpProblem$(\text{'}$kTSP$\text{'},$ LpMinimize$)$

# finish your implementation here

# your code must return a list of k$-$lists $[[0,$ i$1,...,$ il$],[0,$ j$1,...,$jl$],...]$ wherein

# the ith entry in our list of lists represents the

# tour undertaken by the ith salesperson

# your code here

raise NotImplementedError