Problem Background

At the end of the long day, I come before you, you will see my scars, and you will know that I was wounded and have healed. ——Tagore, "Deeply in Love with This City"

Problem Description

Country X has experienced an unprecedented major earthquake, leaving people scarred and the nation in ruins.

To help the people heal and to ensure the survival of Country X, the king has decided to rebuild the nation.

The king has decided to first build \( n \) cities, as he favors odd numbers, \( n \) is an odd number.

After the cities are built, a road needs to be constructed between every pair of cities, totaling \( \frac{n(n-1)}{2} \) roads.

However, the cost of building bidirectional roads is too high. After constructing the \( n \) cities, the remaining funds are only enough to build \( n \) bidirectional roads, and the rest can only be built as unidirectional roads. Fortunately, the direction does not affect the cost of building unidirectional roads, so the direction of all unidirectional roads can be arbitrarily determined.

Additionally, upon completion of the reconstruction, the king has decided to designate 4 cities as the core cities of Country X. To promote the development of Country X, any two of these 4 core cities must be able to reach each other without passing through non-core cities.

The king hopes that you can provide a road construction plan that maximizes the number of ways to choose 4 core cities after the reconstruction.

Input Format

A single line containing a positive integer \( n \) (\( 1 \le n \le 99 \)), guaranteed to be odd, representing the number of cities.

Output Format

The first line contains an integer, representing the maximum number of ways to choose 4 core cities.

The next \( n \) lines each contain \( n \) positive integers describing an adjacency matrix, representing your road construction plan.

Specifically, the \( j \)-th number in the \( i \)-th row being 1 indicates that the \( i \)-th city can reach the \( j \)-th city via a road, and being 0 indicates that the \( i \)-th city cannot reach the \( j \)-th city via a road. We detail three cases:

1. The road between \( i \) and \( j \) is a unidirectional road from \( i \) to \( j \), then the \( j \)-th number in the \( i \)-th row is 1, and the \( i \)-th number in the \( j \)-th row is 0.
2. The road between \( i \) and \( j \) is a bidirectional road, then both the \( j \)-th number in the \( i \)-th row and the \( i \)-th number in the \( j \)-th row are 1. You must ensure that no more than \( n \) bidirectional roads are built.
3. \( i = j \), then the \( j \)-th number in the \( i \)-th row (the \( i \)-th number in the \( j \)-th row) is 0.

Sample Input and Output

Sample Input #1

3

Sample Output #1

0
0 1 1
0 0 1
0 1 0

Sample Input #2

5

Sample Output #2

5
0 1 0 1 1
0 0 1 1 0
1 0 0 0 1
1 0 1 0 1
1 1 0 0 0

Notes

Sample 1 Explanation

Since there are only 3 points, the number of ways to choose 4 core cities is necessarily 0, so just ensure the construction plan meets the conditions.

Sample 2 Explanation

Clearly, any 4 points chosen from the 5 points satisfy the conditions for core cities, so the maximum number of ways is 5.

Data Scale and约定

There are 50 test cases, each worth 2 points. For the \( i \)-th test case, \( n = 2i - 1 \).

For each test case, there are five possible outcomes:

1. Output format error, including: not outputting the maximum number of ways, not outputting the adjacency matrix, outputting extra information, etc. You will receive no points for that test case, and we cannot determine the Special Judge's return result.
2. Incorrectly calculated the maximum number of ways, even if the constructed road plan is correct. You will receive 0% of the points (i.e., 0 points) for that test case, and the Special Judge will return a WA result, with the message "The answer is wrong."
3. Correctly calculated the maximum number of ways but the constructed road plan does not meet the conditions, including: numbers other than 0 or 1 in the adjacency matrix, self-loops, no roads between two cities, more than \( n \) bidirectional roads, etc. You will receive 50% of the points (i.e., 1 point) for that test case, and the Special Judge will return a WA result, with the message "The answer is correct, but your plan breaks the rules."
4. Correctly calculated the maximum number of ways, but the constructed road plan does not maximize the number of ways to choose 4 core cities. You will receive 50% of the points (i.e., 1 point) for that test case, and the Special Judge will return a WA result, with the message "The answer is correct, but your plan is wrong."
5. Correctly calculated the maximum number of ways and correctly constructed the road plan. You will receive 100% of the points (i.e., 2 points) for that test case, and the Special Judge will return an AC result, with the message "The answer is correct."

见题面 Input 部分

见题面 Output 部分