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)~.