90 - The 7th Zhejiang Provincial Collegiate Programming Contest - G
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 "mother-son", and an overcoming or destruction cycle, also known as "grandfather-nephew", of interactions between the phases.
With the two types of interactions in the above graph, any two nodes are connected by an edge.
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:
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.
For each test case, output a line with the number of interactions that are required at least.
Author: XIAO, Dong
Source: The 7th Zhejiang Provincial Collegiate Programming Contest