hackercupai/hackercup

1The far-off land of Tamriel is brimming with opportunity! Opportunity for2adventure, politics, romance... and, perhaps most importantly of all,3commerce.4 5A group of Khajiit merchants, traditionally known for roaming the countryside6selling their wares, have recently set up permanent bazaars in a number of7towns. Having gotten their cat-like paws on a large supply of raw amber and8bronze, they're prepared to strategically work together to maximize their9profits selling it!10 11One bazaar has been set up in each of **N*****M**+1 towns. The towns are12numbered from 0 to **N*****M**, inclusive, and are connected by roads in a13hub-and-spokes arrangement, with town 0 in the center and **N** lines of **M**14towns each arranged around it. The _i_th such line consists of towns15**M***(_i_-1)+1 to **M***_i_, inclusive, connected together in order by16**M**-1 roads (with one between towns **M***(_i_-1)+1 and **M***(_i_-1)+2,17another between towns **M***(_i_-1)+2 and **M***(_i_-1)+3, and so on). For18each line _i_, there is furthermore a road connecting its first town19(**M***(_i_-1)+1) to town 0. Note that each of the **N*****M** roads may be20travelled in either direction, and that each town may be reached from each21other town by following a sequence of roads.22 23For example, if **N**=4 and **M**=2, the arrangement of towns and roads would24look as follows:25 26![]({{PHOTO_ID:291992558607686}})27 28Initially, the bazaar in each town _i_ is stocked with either amber (if **Xi**29= "A") or bronze (if **Xi** = "B"). However, in order to satisfy demand, it30should end up stocked with a potentially different ware, either amber (if31**Yi** = "A") or bronze (if **Yi** = "B"). It's guaranteed that the number of32bazaars initially stocked with amber is equal to the number of bazaars which33should end up stocked with amber (consequently, the same holds true for34bronze).35 36In order to accomplish their goal, the Khajiit merchants may repeatedly select37a pair of towns which are directly connected by a road, and swap their38bazaars' wares. Please help them determine the minimum number of such swaps39required for all **N*****M**+1 bazaars to end up stocked with the required40wares! This is guaranteed to be possible for every possible valid input.41 42### Input43 44Input begins with an integer **T**, the number of Khajiit groups.  45For each group, there is first a line containing the space-separated integers46**N** and **M**.  47Then follows a line with the length-(**N** * **M** \+ 1) string **X**, the48characters **X0** through **XN*M**.  49Then follows a line with the length-(**N** * **M** \+ 1) string **Y**, the50characters **Y0** through **YN*M**.51 52### Output53 54For the _i_th group, print a line containing "Case #_i_: " followed by one55integer, the minimum number of swaps required to stock all of the bazaars with56the required wares.57 58### Constraints59 601 ≤ **T** ≤ 80  611 ≤ **N**, **M** ≤ 1,000,000  621 ≤ **N** * **M** ≤ 1,000,000  63 64The sum of **N** * **M** across all **T** test cases is no greater than6510,000,000.66 67### Explanation of Sample68 69In the first case, no swaps are required.70 71In the second case, bazaars 1 and 2 should swap their goods.72 73In the third case, the bazaars are initially set up as follows (with ones74carrying amber marked in yellow, and ones carrying bronze marked in orange):75 76![]({{PHOTO_ID:266243124686458}})77 78The following sequence of 3 swaps could then be performed to arrive at the79required configuration:80 81![]({{PHOTO_ID:637978470132709}})  82![]({{PHOTO_ID:950762542025264}})  83![]({{PHOTO_ID:635336360404128}})  84 85