As an ACMer, you must have heard of the legend of Ren Pin (RP), which means a person’s lucky degree. Neither can RP be created, nor eliminated without foundation. It can only be transferred from one person to another. Moreover, everyone has his social circle. It’s guaranteed that each person has at least one friend and he cannot be the friend of himself. The relationship is directed. In RP system, one’s RP is transferred from himself to all of his friends uniformly every day. For example, A has three friends, B, C and D and his current RP is 1. In tomorrow, 1/3 of his RP will be transferred to B, 1/3 to C and 1/3 to D and RP from those treat him as friends will be transferred to him as well.
On the other hand, the god in charge of the RP system is tired of the transferring RP from one person to another every day. Making the assumption that the total amount of RP is 1, he wants to know whether there is a stable distribution in RP system, so that by reallocating the RP of each person, he can lighten his workload. Stable distribution means if the structure of social network keeps unchanged, no matter how many days pass by, everyone’s RP keeps unchanged. You will see an example as follows. For the ease of presentation, let “X->Y” denotes X takes Y as his friend. There are only three persons A, B and C in the world with A->B, B->C, C->A and C->B. If the current RPs of A, B, C are 0.2, 0.4, 0.4 respectively, then the RPs will still be 0.2, 0.4, 0.4 in tomorrow. It’s obviously that the distribution keeps unchanged no matter how many days pass by, so (0.2, 0.4, 0.4) is a stable distribution. However, if the current RPs of A, B, C are 0.3, 0.3, 0.4, respectively, then the RPs will be 0.2, 0.5, 0.3 in tomorrow, so (0.3, 0.3, 0.4) is not a stable distribution. The god wonders, for a given a social network, how many stable distributions exist?
Furthermore, if there is one and only one stable distribution, your friend A, who is lack of luck, wants to know whether he can increase his RP by making one more new friend. More specifically, letting RP(A, G) be the RP of A in the stable distribution for a network G, the RP of A after adding A->X to G is RP(A, G \/ {A->X}). Your friend A wants to know if there exists a person X, such that RP(A, G \/ {A->X}) is strictly larger than RP(A, G). For example, there are four persons A, B, C, D in the world with A->B, B->C, C->A, D->A. The only one stable distribution is (1/3, 1/3, 1/3, 0). If A->D is added to the network, the stable distribution will be (2/5, 1/5, 1/5, 1/5) and 2/5 > 1/3, so A can increase his RP by making friend with D. If there are multiple qualifying persons, your friend A wants to know which one can increase his RP to the maximum extent.