trivial 思考题

I am Banach

This is a classic problem by Banach nearly without any change.

There are N boys and M girls. Each boy loves a single girl and each girl loves a single boy. Your task is to divide the boys into two groups A_0 and A_1 and the girls into B_0 and B_1 such that B_1 is the set of the girls liked by boys in A_0 and A_1 is the set of the boys liked by girls in B_0.

According to the Banach Decomposition Theorem there always exists a way. If there are many ways, print any.

Example

Boy_like={1,2,3}
Girl_like={1,3,2}

Then one possible solution is

A0={1}
A1={2,3}
B0={2,3}
B1={1}

Another is

A0={1,2,3}
A1={}
B0={}
B1={1,2,3}

Note that if

Boy_like={1,1,1}
Girl_like={1,2,3}

Then

A0={1,2,3}
A1={}
B0={}
B1={1,2,3}

is NOT a valid answer, but

A0={1}
A1={2,3}
B0={2,3}
B1={1}

is a valid answer.