<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

288. Best Tournament Schedule
time limit per test: 1 sec.
memory limit per test: 65536 KB
input: standard
output: standard



A Go championship is being set up in Petrozavodsk State University. There are many skilled Go players here, including Qc. But this year he decided to join the organizing committee, and try to create a schedule for the tournament.
The championship will be decided in a round-robin tournament, that is, for every pair of players there will be exactly one match between them. Qc has to split the matches in tours in such a manner that no competitor plays twice or more in the same tour. Moreover, the number of tours should be made minimal possible.
As you have probably expected, Qc asked you to do this.

Input
The input contains one integer number N (1 <= N <= 2005) --- the number of participants.

Output
In the first line output an integer number T --- the minimal number of tours. In the following N lines output a NxN matrix containing your schedule. The j-th number in the i-th row of the matrix is the number of the tour for the match between i-th and j-th players, tours being numbered from 1 to T. If i=j, this number should be 0. If there are several optimal solutions, output any.

Sample test(s)

Input
Test #1
4

Test #2
5

Output
Test #1
3
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0

Test #2
5
0 1 5 4 3
1 0 2 3 5
5 2 0 1 4
4 3 1 0 2
3 5 4 2 0
Author:	Anton Golubev, Petrazavodsk SU
Resource:	Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
Date:	August 26, 2005

<|response|>
## 1) Abridged problem statement

Given **N (1 ≤ N ≤ 2005)** players, every pair of players must play **exactly one** match (round-robin). We must assign each match to a **tour (round)** so that **no player plays more than one match in the same tour**.  
Output:

- First line: minimal number of tours **T**
- Then an **N×N** matrix `A`, where:
  - `A[i][j]` = tour number (1..T) when player `i` plays `j`
  - `A[i][i] = 0`
  - `A[i][j] = A[j][i]`

Any optimal schedule is accepted.

---

## 2) Key observations needed to solve the problem

1. Model players as vertices of the complete graph \(K_N\); matches are edges.  
   Assigning tours is exactly **edge coloring**: each color = one tour.

2. Constraint “a player plays at most once per tour” means:  
   all edges with the same color form a **matching** (no shared endpoints).

3. Lower bound on number of tours:
   - Each player has degree \(N-1\), and all incident edges must have distinct colors  
     ⇒ need at least **\(N-1\)** tours.
   - If \(N\) is odd, in any tour one player must be idle (no perfect matching exists)  
     ⇒ need at least **\(N\)** tours.

4. Classic theorem for complete graphs:
   \[
   \chi'(K_N) =
   \begin{cases}
   N-1 & \text{if } N \text{ is even}\\
   N & \text{if } N \text{ is odd}
   \end{cases}
   \]
   So the minimum is:
   - **T = N−1** if N even
   - **T = N** if N odd

5. We can explicitly construct an optimal schedule using the **circle (round-robin) method** in \(O(N^2)\), which is fine for \(N \le 2005\).

---

## 3) Full solution approach

We build tours one by one and fill a matrix `A`.

### Case A: N = 1
No matches exist, so **T = 0** and matrix is `[0]`.

### Case B: N is odd → T = N
Arrange players `0..N-1` on a “circle/table” of size `N`.

For each round `r = 0..N-1`:
- Pair symmetric positions:
  - For `i = 1..(N-1)/2`:
    - `p1 = (i - r) mod N`
    - `p2 = (N - i - r) mod N`
  - Set `A[p1][p2] = A[p2][p1] = r+1`

Each round creates \((N-1)/2\) matches (one player is effectively idle), and across all rounds every pair appears exactly once.

### Case C: N is even → T = N−1
Use the same method, but it’s more convenient to rotate an **odd** number of seated players:

- Let `table_size = N-1` (players `0..N-2` sit on the circle)
- Player `N-1` is “standing”
- For each round `r = 0..N-2`:
  1. Standing player plays the “head”:
     - `head = (table_size - r) mod table_size`
     - set `A[head][N-1] = A[N-1][head] = r+1`
  2. Pair remaining seated players symmetrically (same as odd-case but modulo `table_size`):
     - for `i = 1..(table_size-1)/2`:
       - `p1 = (i - r) mod table_size`
       - `p2 = (table_size - i - r) mod table_size`
       - set `A[p1][p2] = A[p2][p1] = r+1`

Now every round is a **perfect matching** (all N players play exactly once), and all pairs occur exactly once over `N-1` rounds.

### Complexity
- We assign exactly one tour number per edge ⇒ \(O(N^2)\) time.
- Output is \(O(N^2)\).
- Memory: matrix `N×N` of ints; for N=2005 this is acceptable in typical limits.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // Special case: N = 1 -> no matches
    if (n == 1) {
        cout << 0 << "\n";
        cout << 0 << "\n";
        return 0;
    }

    // Minimal number of tours for K_n edge-coloring:
    // even n -> n-1, odd n -> n
    int T = (n % 2 == 0) ? (n - 1) : n;
    cout << T << "\n";

    // For even n, we rotate only n-1 players (odd count), last player is "standing".
    // For odd n, we rotate all n players.
    int table_size = (n % 2 == 0) ? (n - 1) : n;

    // schedule[i][j] = round number when i plays j; diagonal remains 0.
    vector<vector<int>> schedule(n, vector<int>(n, 0));

    // Build each round
    for (int r = 0; r < T; r++) {

        // Even case: also pair the standing player (n-1) with the current head on the table
        if (n % 2 == 0) {
            int head = (table_size - r) % table_size;
            schedule[head][n - 1] = r + 1;
            schedule[n - 1][head] = r + 1;
        }

        // Pair symmetric seated players on the rotating table
        int half = (table_size - 1) / 2;
        for (int i = 1; i <= half; i++) {
            // We rotate by r; use modular arithmetic.
            // In C++, (a % m) can be negative, so normalize by adding table_size.
            int p1 = (i - r) % table_size;
            if (p1 < 0) p1 += table_size;

            int p2 = (table_size - i - r) % table_size;
            if (p2 < 0) p2 += table_size;

            schedule[p1][p2] = r + 1;
            schedule[p2][p1] = r + 1;
        }
    }

    // Output the matrix
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j) cout << ' ';
            cout << schedule[i][j];
        }
        cout << "\n";
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0])

    # N = 1: no matches
    if n == 1:
        sys.stdout.write("0\n0\n")
        return

    # Minimal number of tours:
    # even n -> n-1, odd n -> n
    T = n - 1 if (n % 2 == 0) else n

    # Table size used for rotation:
    # even n -> rotate n-1 players, keep last as "standing"
    # odd n -> rotate all n players
    table_size = n - 1 if (n % 2 == 0) else n

    # NxN schedule matrix
    schedule = [[0] * n for _ in range(n)]

    # Construct rounds
    for r in range(T):
        # Even case: match standing player (n-1) with the current head
        if n % 2 == 0:
            head = (table_size - r) % table_size
            schedule[head][n - 1] = r + 1
            schedule[n - 1][head] = r + 1

        # Pair symmetric players on the table
        half = (table_size - 1) // 2
        for i in range(1, half + 1):
            p1 = (i - r) % table_size
            p2 = (table_size - i - r) % table_size
            schedule[p1][p2] = r + 1
            schedule[p2][p1] = r + 1

    # Output
    out = [str(T)]
    for i in range(n):
        out.append(" ".join(map(str, schedule[i])))
    sys.stdout.write("\n".join(out) + "\n")

if __name__ == "__main__":
    main()
```

These implementations follow the proven optimal construction and satisfy all constraints.