Stepping into the chamber E, Little Graphy and her friend find the Black Dark Witch packaging up some prone grass.
“Black Witch!” yells Pinky, “I’ m gonna burnnnn youuuu!”
“Impressing, really impressing. Many people have died in this cavern,” says the Black Dark Witch.
“However, can you escape again?” she smiles, and disappears into thin air.
“Wai…, ” a laser shoots through Pinky’s body before she finishes her word.
“Pinkyyyyyyyyyyyyyyyyyyy!” cries Blues, “No one will be willing to go scuba diving wi…wow!!” Not until Little Graphy pulls Blues down does he find that the laser gun has been aimed at him.
“Chuchu! I almost get killed!” Blues cries again, “We have to shut this thing down!”
“Well, I think I’ve find the way to turn off the laser gun,” says Little Graphy.
“There’re n red stones and m blue stones on the floor, and there’re some links between some pairs of red and blue stones.”
“Everytime the laser gun shoots, one of the link shines.”
“I think we should destroy some stones in such a way that at least one stone is destroyed in each pair.”
“However, we don’t have lots of time to destroy them, we should spend as less time as possible!”
Can you help Little Graphy figure out the fastest way of destroying stones?
The first line is an integer T indicating that there’re T test cases.
There’re three integers n, m, k in the first line of each test case, which means there’re n red stones, m blue stones, k pairs of links. The second line contains n integers, the ith integer Ri means red stone i will take Ri seconds to destroy. The third line contains m integers, the ith integer Bi means blue stone i will take Bi seconds to destroy. Each of the next k line contains a pair (a, b) means that there is a link between red stone a and blue stone b.
Output three lines for each test case. The first line should contains an integer indicating the minimum time Little Graphy needs. The second line contains an integer A and followed by A accending integer represending the number of red stones to be destroyed and which red stones should be destroyed. The third line contains an integer B and followed by B accending integer represending the number of blue stones to be destroyed and which blue stones should be destroyed.