Two-coach trip

Split the students of a school trip between two coaches so that neither coach is more crowded than it has to be.

There are n students numbered 0 to n - 1, and each must ride exactly one of two coaches. Coaches have no seat limit and may even be empty.

• Every pair in rivals is a pair of students who must not ride the same coach.
• Every pair in friends is a pair of students who must ride the same coach.

Rules apply even indirectly: if 0 and 1 are friends and 1 and 2 are friends, then 0 and 2 ride together as well. A pair may be listed more than once, and a student can never be a rival of themself.

Input: n, the number of students, rivals, a list of [a, b] pairs, and friends, a list of [a, b] pairs.

Output: the smallest possible number of students on the fuller coach over all valid ways to assign the students, or -1 if no valid assignment exists. Both coaches have to be counted, so with n = 5 and no rules at all the answer is 3.

Many students can be completely unconstrained, and there can be a great many independent groups, so trying every assignment of groups to coaches will be too slow.