문제<\/h2>
There are two fenced areas next to each other: one houses a group of pigs, and the other houses a herd of giraffes. While pigs cannot visit the giraffes, and giraffes cannot visit the pigs, they can communicate over the fence. In fact, they have become such good friends that pigs prefer to talk to giraffes instead of other pigs, and giraffes feel the same way—they would rather talk to pigs than to other giraffes.<\/p>
This relationship is mutual: if a pig likes to talk to a specific giraffe, that giraffe likes to talk back to that same pig. However, no pig likes to talk to another pig, and no giraffe likes to talk to another giraffe.<\/p>
If an animal wants to send a message to another animal, even if it doesn’t like to talk to it directly, it can do so by passing the message through other animals. Messages can only be passed between animals that like to talk to each other.<\/p>
To quantify the amount of chatter, we define the noise level<\/em> between two animals as the minimum number of talks required for a message to be passed from the source animal to the target animal. If a message cannot be passed between two animals, the noise level for that pair is $0<\/mn><\/mrow>0<\/math><\/span><\/span> 0<\/span><\/span><\/span><\/span>. For instance, if two animals like to talk directly to each other, their noise level is 1<\/mn><\/mrow>1<\/math><\/span><\/span> 1<\/span><\/span><\/span><\/span>. If the message must pass through one other animal, the noise level is 2<\/mn><\/mrow>2<\/math><\/span><\/span> 2<\/span><\/span><\/span><\/span>, and so on.<\/p> We are interested in the total noise level, which is the sum of noise levels for all unordered pairs of different animals. Note that the noise level between two different animals is only counted once.<\/p> The problem is, the number of animals keeps increasing. New animals are born by combining the properties of two existing animals of the same kind, referred to as the parents. The new animal will belong to the same kind as its parents (pig or giraffe). Additionally, the newborn animal can immediately start talking to other animals.<\/p> The newborn animal likes to talk to exactly the animals that like to talk to exactly one of its parents. Along with the initial setup of animals and their talking preferences, you will be given a sequence of queries describing the birth of new animals. After each animal is born, your task is to calculate the total noise level.<\/p> 입력<\/h2> The first input line contains three integers A<\/mi><\/mrow>A<\/math><\/span><\/span> A<\/span><\/span><\/span><\/span>, B<\/mi><\/mrow>B<\/math><\/span><\/span> B<\/span><\/span><\/span><\/span>, M<\/mi><\/mrow>M<\/math><\/span>$

Pigpartite Giraffe