WITTY - THE N WITTY FRIENDS
N witty friends went for an outing trip. During the outing they have spent lot of money in lot of places. In some places, a friend (A) spends ‘M’ money for his friend (B).
An expense is described by "A spends M$ for B"
A transaction is described by “X gives K$ to Y”
You are given all the expenses made by the friends. The outing trip is ended and now you have to find the minimum transactions to be made by the friends to tally the expenses.
The first line consists of an integer t, the number of testcases. For each test case, the first line consists of an integer N, the number of expenses made by friends followed by N lines. Each line contains two strings A and B (A!=B) and an integer m, the money A spent for B.
For each test case, print the minimum number of transactions required to tally the expenses.
Each character in A is either 'A' or 'B'
Each character in B is either 'A' or 'B'
1<= length of A,B <=2
AA BB 10
A BB 100
BB AA 100
AA A 100
AB BA 100
BA B 100
AB B 100
B A 200
Explanation of Testcases:
Case 1: AA spent 10$ for BB. So one transaction "BB gives 10$ to AA" is needed to tally the expense.
Case 2: A spent 100$ for BB, BB spent 100$ for AA and AA spent 100$ for A. In this case, no transactions are required as the expenses are already tallied.
Note: Note that A can spend for B at many places.