In class, we saw that the Propose$-$and$-$reject algorithm terminates in at most n$2$ rounds when there are n families and n animals.

$($a$)$ It seems possible that the algorithm may complete in fewer rounds if the preference lists have a certain structure. Describe a class of preference lists, one for each value of n$,$ such that the propose$-$and$-$reject algorithm will complete in only O$($n$)$ rounds when run on these preference lists.

More specifically, your solution should do the following: for an arbitrary positive integer n$,$ give a precise description $($one way to think of $$precise$$ is to describe it in a way that could be imple$-$ mented in code by an intro student$)$ of preference lists for n families and n students. Let T$($n$)$ be the number of rounds that the propose$-$and$-$reject algorithm takes for these preference lists. Prove that T$($n$)$ is O$($n$).$