Welcome to ZOJ
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.

Sample Input

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