Let $F$ be the number of different possible friendships. There's one for each unordered pair of users, meaning that $F=\frac{N(N-1)}{2}$. $F$ is small enough (only $15$ when $N=6$) that it's viable to consider each possible subset of these friendships. There are $2^F$ such subsets, and we can consider all of them using depth-first search (recursion), or by iterating over all bitmasks from $0$ to $2^F-1$.

For each considered set of friendships, we can then compute its resulting grid of mutual friend counts by iterating over all $\mathcal{O}(N^2)$ pairs of users $(i,j)$, and counting the number of other users $k$ such that the set of friendships includes both unordered pairs $(i,k)$ and $(j,k)$. This process takes $\mathcal{O}(N^3)$ time. If the resulting grid of mutual friend counts exactly matches the required grid $M$, then we've found a valid set of friendships, meaning that we can output it and stop the depth-first search. If we finish considering all $2^F$ possible sets of friendships without coming across a valid one, then the answer must be Impossible.

The time complexity of the algorithm described above is $\mathcal{O}(2^F{N}^3)$.