There are N patients (numbered from 0 to n — 1) who want to visit the doctor. The doctor has S possible appointment slots, numbered from 1 to S. Each of the patients has two preferences. Patient K would like to visit the doctor during either slot A[k] or slot B[k]. The doctor can treat only one patient during each slot.
Is it possible to assign every patient to one of their preferred slots so that there will be at most one patient assigned to each slot?
Input: Two arrays A and B, both of N integers, and an integer S
1 <= N <= 10^6
1 <= S <= 2*10^6
1 <= A[i] <= S
1 <= B[i] <= S
no patient has two preference for the same slot i.e.
A[i] != B[i]
"true" if it is possible to assign every patient to one of their preferred slots, one patient to one slot, and