Checking if several sets of pairs covers a given set of pairs
Here are some hints.

First, reduce your problem to the following one: given a collection of $N$ subsets $A_1,\ldots,A_N \subseteq [N]$, determine if there is some permutation $\pi$ such that $\pi(i) \in A_i$.

Given the $A_i$, construct a bipartite graph in which node $i$ on the left is connected to node $j$ on the right if $i \in A_j$. A permutation $\pi$ such that $\pi(i) \in A_i$ exists iff this graph contains a perfect matching. We know how to test whether a bipartite graph contains a perfect matching efficiently.