Students are assigned to different cubicles, arranged in a circle for various positive academic and social purposes. Each cubicle therefore is adjacent to two other cubicles, one on the right, and one on the left. Assume there are n students, and each one has a list of people to whom they would not object being assigned nearby. The CS Seating Problem asks whether or not the students can be arranged in a circle without violating any of their preferences.

a$.$ Prove that the problem is NP$-$Complete, even if each list contains at most three students. Hint: Reduce from the Hamiltonian Circuit problem which is NP$-$complete even for graphs of degree $3.$

b$.$ Describe an algorithm to solve the problem when each list has at most two students.