$(25$ points$)$

As a suburban planner, you need to place k houses in Ladhaland numbered $1$ to k in a k $\backslash$times k grid.

However, you are given two lists of house pairs labeled textttrowConstraints and colConstraints

of length m and n respectively. For a pair $($a$,$ b$)$ in rowConstraints, there is a requirement

that house a must be in a row strictly above the row that house b is in$.$ For a pair $($a$,$ b$)$ in

colConstraints, there is a requirement that house a must be in a column strictly to the left of

the column that house b is$.$

Design an algorithm that returns the row and column coordinates for each of the k houses given

the number of houses k$,$ rowConstraints, and textttcolConstraints. If it is impossible to fulfill

all the requirements in textttrowConstraints and colConstraints, return texttt$$Impossible$.$

Provide a correctness and runtime analysis