A lighthouse crew 0 .. n-1 is split into a day shift (0) and a night shift (1). Each pair (a, b) in handovers must be on different shifts (one hands the logbook to the other). A few people have already chosen: fixed maps a person to the shift they insist on.
Implement assign_shifts(n, handovers, fixed) -> list[int] | None: return a list of n shifts (each 0 or 1) that respects every handover pair and every fixed choice, or None if that's impossible. People with no constraints can go on either shift. Any valid answer is accepted.
assign_shifts(4, [(0, 1), (1, 2)], {2: 0}) # [0, 1, 0, 0] (person 3 could be 1 as well)
assign_shifts(3, [(0, 1), (1, 2)], {0: 0, 2: 1}) # None: 0 and 2 must share a shift
assign_shifts(3, [(0, 1), (1, 2), (2, 0)], {}) # None: odd cycle
Constraints: 1 <= n <= 10^5, up to 2 * 10^5 handovers, fixed has at most n entries. A pair (v, v) can never be satisfied.
Show hint
in each connected group the colouring is forced up to a swap. BFS each group from a fixed person if it has one (using their shift), otherwise from anyone with shift 0; then check every edge and every fixed person.