In the Splitwise app, people form groups and add the expenses of members of the group. This is especially useful for vacations, where people traveling in a group can maintain an account of their expenses and who paid the bills. All people in the group are assigned distinct IDs between 1 and N, where N is the size of the group. In addition to keeping a record of the expenditure, Splitwise also calculates the list of shortest-path transfers (defined later) that will settle up all dues. Each transaction has the following parameters:- transaction_id - It is a string representing the unique ID by which the transaction is identified. paid by - It is a list of lists, where each element of the list is another list having the form [x, y]. Here, x and y denote that person having ID x paid Rs. y. split as- It is a list of lists, where each element of the list is another list having the form [x, y]. Here, x and y denote that after all dues are settled, a person having ID x will ultimately contribute Rs. y to the transaction. For any given transaction, the following condition holds true:- person having ID x will ultimately contribute Rs. y to the transaction. For any given transaction, the following condition holds true:- Total amount paid = Sum_of_all_splits In other words, the sum total of all amounts in list paid by equals the sum total of all amounts in list split_as. Following is the example of a transaction in a group of size N-64:- transaction_id: "#f1230" paid_by: [[1, 30], [4, 100], [63, 320]] split_as: [[1, 120], [2, 20], [3, 40], [4, 40], [37, 100], [51, 40], [53, 90]] . Shortest-Path Transfers: Shortest-path transfers lead to a reduction in the number of transfers. Specifically, for a group having multiple transactions, the shortest-path transfers will be a list of payments to be made such that:- Each payment can be represented by a list of the following form:- [payer_id, payee_id, amount]. There is only 1 payer, and 1 payee in each payment. which are distinct from each other. So, payer_id #payee_id, for any payment. Each person (out of the N people) can only either be the payer (in all payments involving him), or the payee, but not both. The total amount of money that each person should receive/spend, must be N payment. Each person (out of the N people) can only either be the payer (in all payments involving him), or the payee, but not both. The total amount of money that each person should receive/spend, must be equal to the total amount he would receive/spend according to the given list of transactions. Clearly, there can be several shortest-path transfers for a particular list of transactions. Specifically, the lexicographically smallest shortest path has the following:- Arrange people who have borrowed money in ascending order of their IDs. Do the same for people who have lent money. . Now, construct payments so that the least borrower ID has to pay the least lender ID. Continue this process, till all debts have been settled. Task Given N members in a group, and lists representing the transactions(expenses), print the payments involved in the lexicographically smallest shortest-path transfers for the group. Example Input: N = 4 5 transactions, that can be represented as follows:- New Example Input: N = 4 . 5 transactions, that can be represented as follows:- o transaction_id = "#a1234", paid_by = [[1, 60]], split_as= [[2, 60]]. transaction_id = "#a2142", paid_by = [[2, 40] ], split_as= [[3, 40]]. transaction_id = "#b3310", paid_by=[[3, 30]], split_as= [[4, 30]]. o transaction_id = "#b2211", paid_by = [[4, 30]], split_as= [[3, 30]]. transaction_id = "#f1210", paid_by = [[3, 20]], split_as= [[1, 20]] Output: 2 payments (of the form [payer_id, payee_id, amount) are to be made, represented by the list:- [[1, 2, 20], [1, 3, 20]] Approach: The given list of payments satisfies all three necessary conditions. Hence, it is a Shortest-Path Transfer Function description Complete the function solve provided in the editor. This function takes the following 2 parameters and returns the required answer: 4 5 The given list of payments satisfies all three necessary conditions. Hence, it is a Shortest-Path Transfer. Function description Complete the function solve provided in the editor. This function takes the following 2 parameters and returns the required answer: N: An integer, representing the number of people in the group. transaction_list: A list (vector) of transactions. Each transaction is a dictionary, having keys "transaction_id", "paid_by" and "split_as". (The contents of each transaction are explained above) Input format Note: This is the input format that you must use to provide custom input (available above the Compile and Test button). The first line contains two space-separated integers N and M, the number of people in the group, and the number of transactions recorded. The next lines describe the M transactions as follows:- o Each new transaction begins from a new line. o The first line of each transaction contains a string, representing the transaction_id of the transaction. o The 2nd line of each transaction contains 2 space-separated integers n_payers and n_splits. n_payers denotes the number of people in the paid by list. n_splits denotes the number of people in the split as list. denotes the number of people in the split as list. o The next n_payers lines contain two space-separated integers, the payer and the amount paid. The next n_splits lines contain two space-separated integers, the borrower and the amount borrowed. Output format Print the answer in the given format. . In the first line, print a single integer K, denoting the number of payments involved in the Shortest Path Transfer. The next K lines should represent the K payments. Each payment should be printed in a single line as 3 space-separated integers payer_id, payee_id, and amount. Here, payer_id is the ID of the person who needs to pay the amount of money to the person with ID payee_id. Constraints 2 N 2* 105 . 1 M 5000 . . 1 < len(transaction[i][paid_by]) + len(transaction[i][split_as]) 50 1 total_money_exchanged_in_each_transaction 107 65 Sample input #itsmylife Sample output 1 2 75 1 4 13 1 total_money_exchanged_in_each_transaction < 107 Sample input 65 #itsmylife 23 1 25 3 15 4 10 5 25 65 #itsnow 14 View more Explanation E Sample output Time Limit: 1.0 sec(s) for each input file Memory Limit: 256 MB 4034 10 1 2 75 1 4 13 3 4 12 3 5 18 3 6 20 The following test cases are the actual test cases of this question that may be used to evaluate your submission. Note: Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement. Limits Auto-complete ready! 1 #include 2 3 4 using namespace std; int main() { 5 6 int num; cin >> num; Save //Reading input from STDIN cout < < "Input number is " < < num < < endl; // Writing output to STDOUT 7 } Test against custom input Custom input populated C++14 (g++ 10.3.0) Compile & Test code E * 1:1 vscode Submit code