Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3933
Team Formation

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

For an upcoming programming contest, Edward, the headmaster of Marjar University, is forming several two-man 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 high-performance teams. A high-performance 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 high-performance teams as possible and at the same time maximize the number of girls in the teams.

#### Input

There 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 i-th character is 0 then i-th 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 i-th character is 0 then i-th 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 i-th student.

#### Output

For each case, output two integers a and b denoting the number of high-performance teams and the number of girls.

In the next a lines, each contains two integers xi and yi denoting the students in i-th team.

If there are multiple solutions, you can output any of them.

```1
3
101
000
0
0
0
```

#### Sample Output

```1 2
1 2
```

Author: LIN, Xi
Source: The 16th Zhejiang University Programming Contest
Submit    Status