
90  The 7th Zhejiang Provincial Collegiate Programming Contest  G
Introduction The Wu Xing, or the Five Movements, Five Phases or Five Steps/Stages, are chiefly an ancient mnemonic device, in many traditional Chinese fields. The doctrine of five phases describes two cycles, a generating or creation cycle, also known as "motherson", and an overcoming or destruction cycle, also known as "grandfathernephew", of interactions between the phases. Generating:
Overcoming:
With the two types of interactions in the above graph, any two nodes are connected by an edge. Problem In a graph with N nodes, to ensure that any two nodes are connected by at least one edge, how many types of interactions are required at least? Here a type of interaction should have the following properties:
Input For each test case, there's a line with an integer N (3 <= N < 1,000,000), the number of nodes in the graph. N = 0 indicates the end of input.Output For each test case, output a line with the number of interactions that are required at least. Sample Input 5 0 Sample Output 2 Reference http://en.wikipedia.org/wiki/Wu_Xing Author: XIAO, Dong Source: The 7th Zhejiang Provincial Collegiate Programming Contest 