Soldiers & Terrorists
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.
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.
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.
1 1 2 3
2 3 1 1
Problem Setter: Kaustubh Karkare