$5$ We Are Cooking! $(10$ points$)$

Suppose you and your friend Jamie live, together with $n-2$ other people, at a popular off$-$campus cooperative apartment, the Academy on Charles. Over the next $n$ nights, each of you is supposed to cook dinner for the co$-$op exactly once, so that someone cooks on each of the nights.

Of course, everyone has scheduling conflicts with some of the nights $($e$.$g$.,$ exams, concerts, etc.$),$ so deciding who should cook on which night becomes a tricky task. For concreteness, let's label the people

$\{p_1,$dots,$p_n\},$

the nights

$\{d_1,$dots,$d_n\}$

and for person $p_i,$ there's a set of nights $S_i$sub$\{d_1,$dots,$d_n\}$ when they are not able to cook.

A feasible dinner schedule is an assignment of each person in the co$-$op to a different night, so that each person cooks on exactly one night, there is someone cooking on each night, and if $p_i$ cooks on night $d_j,$ then $d_j!in{S}_i.$

$($a$)$ Describe a bipartite graph $G$ so that $G$ has a perfect matching if and only if there is a feasible dinner schedule for the co$-$op$.$

$($b$)$ Your friend Jamie takes on the task of trying to construct a feasible dinner schedule. After great effort, she constructs what she claims is a feasible schedule and then heads off to class for the day.

Unfortunately, when you look at the schedule she created, you notice a big problem. $n-2$ of the people at the co$-$op are assigned to different nights on which they are available: no problem there. But for the other two people, $p_i$ and $p_j,$ and the other two days, $d_k$ and $d_l,$ you discover that she has accidentally assigned both $p_i$ and $p_j$ to cook on night $d_k,$ and assigned no one to cook on night $d_l.$

You want to fix Jamie's mistake but without having to recompute everything from scratch. Show that it's possible, using her "almost correct" schedule, to decide in only $O(n^2)$ time whether there exists a feasible dinner schedule for the co$-$op$.($If one exists, you should also output it$.)$