Problem
I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive.
Example
Left vertices: $a,b,c$
Right vertices: $x,y,z$
Edges: $(a,x),(a,y),(b,z),(c,y)$
Exlusive pairs: $(b,z)$ and $(c,y)$
Answer: no perfect matching
Question
Is the problem in P or NP?
Solution Attempts
I know that Perfect Matching in Bipartite Graph Problem is in P. But I cannot find a polynomial-time algorithms for the above version of this problem. I have also tried proving that it is NP, but without any luck.