GREED - Greedy island


Gon is on Greedy island. He wants to go home. But to get the ticket to leave the game, he has to get N cards labeled in a sequence from 1 to N (the order of the cards in his hand is irrelevant). He already has N cards, but not forming a sequence from 1 to N. So he wants you to help him. For some cards, he can change one card for another for one piece of gold. Help him to get the ticket at the minimum cost (using the minimum number of exchanges).

Input

The first line contains t, the number of tests (1<=t<=10). For each test case:

  • the number of cards N is given is given in the first line (2<=N<=500).
  • the next N lines contain the N cards owned by Gon.
  • the following line contains e, the number of different allowed types of exchanges.
  • the next e lines contain two integers xi,yi each which mean that we can exchange and replace the card marked x by the card marked y and vice versa.

There is a blank line after each test case.

Output

For each test case, output a line denoting the minimum required cost.

Example

Input:
1
4
1
2
2
2
2
2 3
3 4

Output:
3

hide comments
Abdelrahman Atia: 2017-03-14 21:14:16


take care of edges count > 80000
kept getting runtime error

paras meena: 2015-11-05 05:49:59

HunterXHunter :D (y)

Deepak Gupta: 2014-11-07 18:28:53

numbers on cards seem to be >500
99999 worked for me

Ghost Of Perdition: 2013-09-02 21:06:56

can you swap between two cards in your hand? and what is the cost?

Rocker3011: 2013-01-15 03:38:57

i thought a problem about HunterxHunter and greed island... but someone beated me, 8 years before

Noszály Csaba: 2011-08-23 19:13:16

@~neo~
there is 1 testcase:
you have 4 cards numbered 1 2 2 2
there are 2 allowed exchange 2<->3 and 3<->4
so
leave the first two card as it is,
change the third card (it is 2) to 3 (1 gold),
then change the fourth card (it 2 too ) to 3 (1 gold) ,then change this (3) to 4 (1 gold)
it is easy to see that fewer gold is not enough, so output 3 :-)

Last edit: 2011-08-23 19:54:37
~neo~: 2011-08-03 14:22:10

can anyone explain the above test case..!!


Added by:Le Trong Dao
Date:2005-06-08
Time limit:50s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Mr.Tran Minh Quan