Question $2$: The Good Host $...$

You are hosting a party for $\backslash ($ n $\backslash )$ people $($indexed $\backslash (1,2,\backslash$ldots$,$ n $\backslash ))$ and you have booked two banquet halls. As it turns out, there are some some pairs of people that simply do not see eye$-$to$-$eye and they refuse to be in the same hall at the same time. Given a list of pairs $\backslash (\backslash \{$i$,$ j$\backslash \}\backslash )$ that don't get along, your goal is to find a partitioning of the $\backslash ($ n $\backslash )$ people into two halls so that within each hall, there is no pair that does not get along. $($If this is impossible to achieve, your algorithm must output impossible.$)$

Give an algorithm for this problem that runs in time $\backslash ($ O$($m$+$n$)\backslash ),$ where $\backslash ($ m $\backslash )$ is the number of pairs $\backslash (\backslash \{$i$,$ j$\backslash \}\backslash )$ of people who do not get along.

Important. To receive full credit, you must describe your algorithm in pseudocode and give an explanation for why it runs in $\backslash ($ O$($m$+$n$)\backslash )$ time.

$[$Hint: Form an appropriate graph and try a BFS$-$like procedure.$]$