All Submissions


Problem Statement

The Army has just discovered the location of a terrorist base where they are holding a young girl hostage. A team of soldiers has to be sent to rescue the damsel in distress and your job is to determine the size of this team.
Surveillance using a UAV has given you information about the number the number of terrorists and details about how they are guarding the base. Terrorists are not only keeping track of what is going on outside, but they are also keeping a watch on each other. If two terrorists are watching over each other, and one of them is shot down, the other will raise an alarm, and the girl will be killed. Thus, they both will need to be simultaneously terminated, requiring at least 2 soldiers.
While your soldiers are sufficiently camoflagued that they will not be detected as they approach the base, there do need to be enough of them in order to take out all terrorists without raising the alarm.

Input Specifications

The first line of input contains the number of test cases.
Each test case consists of 3 lines.
The first line has a single integer N (1<=N<=100) indicating the number of Terrorists.
The second line (X) & the third line (Y) contain the same number of integers. For each pair of integers Xi & Yi (1<=Xi,Yi<=N), Terrorist Xi is watching over Terrorist Yi.

Output Specifications

Corresponding to each testcase, print a single integer (on its own line) which equals the number of soldiers required to be able to eliminate all terrorists and rescue the girl.

Sample Input


2
2
1 2
2 1
3
1 1 2 3
2 3 1 1
2
1
2


Sample Output


2
3
1


Problem Setter: Kaustubh Karkare

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0