Airlines - 2
Oh! Bytelandavia, once the sole airline in Byteland, has gone bankrupt and now several new companies are after their contracts. Byteland's Civil Aviation Office (CAO) wants to minimize their number, but without hurting the established timetables.
There are N airports in Byteland, and so far there have been direct flights in both directions between all pairs of them. The officials of the CAO want to preserve this situation, but for each pair of airports they want all flights between them be operated by a single company.
The second requirement of the CAO is harder to understand, but it is mandatory none the less (they are not pushing their papers for nothing)...
So, the requirement is that a traveler is not allowed to make a round trip (returning to his starting airport) using only planes of a single company if he makes intermediate stops in an even number of airports. For example, if he has to fly from New Vasiuky to Old Moscow, then to Vovinburg and then return to New Vasiuky, he will have to use at least two different companies. However, if he would also pass through New Bobruisk, there would be no such requirement.
Determine the minimal number of airline companies needed to fulfill the requirements of the CAO. Find also one possible division of the flights between the new companies.
Input
The only line of input contains N — the number of airports in Byteland (2 ≤ N ≤ 500).
Output
The first line of output should contain K, the number of airline companies. N-1 lines should follow. The i-th of these lines (1 ≤ i ≤ N-1) should contain N-i integers. The j-th integer of the i-th line should denote the airline company that operates flights between the airports i and i+j. Both the companies and the airports are numbered starting from 1.