
ZOJ Problem Set  3933
For an upcoming programming contest, Edward, the headmaster of Marjar University, is forming several twoman teams from students of his university. There are n students in the university numbered from 1 to n. There are two groups of students in the university and each student belongs to exactly one of the groups. For each student in the university, he/she has a list of students whom he/she will never form a team with. For two students a and b, if b is in a's list, a is also in b's list. Edward will only form highperformance teams. A highperformance team is a team which consists of two students from different groups who are willing to form a team. In addition, Edward wants as many as possible girls to participate in the contest. You, as Edward's secretary, need to form as many highperformance teams as possible and at the same time maximize the number of girls in the teams. InputThere are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case: The first line contains an integer n (1 ≤ n ≤ 500)  the number of students. The second line contains a binary string of length n. If the ith character is 0 then ith student is in the first group, otherwise the student is in the second group. The third line contains a binary string of length n. If the ith character is 0 then ith student is a girl, otherwise the student is a boy. In the following n lines, each line starts with an integer m followed with m distinct integers, denoting the list of ith student. OutputFor each case, output two integers a and b denoting the number of highperformance teams and the number of girls. In the next a lines, each contains two integers x_{i} and y_{i} denoting the students in ith team. If there are multiple solutions, you can output any of them. Sample Input1 3 101 000 0 0 0 Sample Output1 2 1 2 Author: LIN, Xi Source: The 16th Zhejiang University Programming Contest 