<|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.

164. Airlines
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



Microland country has very big territory, so its citizens always travel by air between cities. This is why transporting people by air is very profitable in Microland, and some years ago there was exactly one direct air flight between any two cities and there had survived only one air company, "Microland airlines". But then some Microland states suited it for violating the antitrust law and, according to the decision of the court, that company was divided into M independent parts, which later become known as "Microland airlines 1", "Microland airlines 2" and so on. Every flight previously owned by "Microland airlines" became owned by exactly one of its parts.

Now the president elections are coming in this country. To increase his rating, current president of Microland decided to buy some parts of "Microland airlines" and make flights of these companies free. He wants to make it easier to travel from any city to any, so for any two cities he wants to make it able to fly from one to other making not more than 2 changes, i.e. using not more than 3 free flights. In other words, for any two cities A and B: direct flight between these cities must be done free, or there must exist a city C so that flights from A to C and from C to B will be done free, or there must exist two cities C and D so that flights from A to C, from C to D, from D to B will be done free. But, of course, the president is avoid of breaking that antitrust law (the court is really independent in Microland!). Not to violate it, president has to buy not more than ((M+1) div 2) "Microland airlines" parts.

You are working in president's team. You are to write a program that will decide, what parts of "Microland airlines" the president should buy.

Input
On the first line of input there are two integers N and M (1<=N<=200) --- the number of cities in Microland and the number of "Microland airlines" parts. Next N lines contain N integers each. i-th integer in i-th line is 0; and j-th, if j<>i, is the number of "Microland airlines" part which owns direct flight from i-th city to j-th (and from j-th to i-th too). Each "Microland airlines" part owns at least one flight.

Output
If the solution exists, write on the first line of output one integer --- the number of "Microland airlines" parts that should be bought by president. On the second line of output write the numbers of these parts in any order. If several solutions exist, output any. If no solutions exist, output only one integer "-1".

Sample test(s)

Input
4 3
0 3 2 2
3 0 1 2
2 1 0 1
2 2 1 0

Output
2
1 3
Author:	NNSU #2 team
Resource:	Lazurny olympiad in informatics, 2002
Date:	July-August 2002

<|response|>
1. **Abridged problem statement**

- There are \(N\) cities and \(M\) airline companies.
- Between every pair of distinct cities \(i, j\) there is exactly one direct flight, owned by a company \(c(i,j) \in \{1,\dots,M\}\). Symmetric: flight \(i \leftrightarrow j\) has same company.
- The president may buy some companies; all flights of bought companies become free.
- Using only free flights, any city must be reachable from any other in **at most 3 flights** (0, 1, 2, or 3 edges; up to 2 changes).
- Antitrust restriction: he may buy at most \(\left\lfloor \dfrac{M+1}{2} \right\rfloor\) companies.
- Goal: choose some companies (indices) satisfying both constraints, or print `-1` if impossible.

---

2. **Key observations**

1. **Graph model**

   - Cities: vertices \(1..N\).
   - For each unordered pair \(\{i,j\}\), there is one edge labeled with company \(c(i,j)\).
   - If we choose a company set \(S\), the *free-flight subgraph* is the graph with all edges whose label is in \(S\).
   - Requirement: the *graph diameter* of this subgraph must be \(\le 3\) (distance between any two vertices at most 3).

2. **Always possible in 2-color case**

   Suppose we only had 2 companies (2 colors): black and white.
   Then edges of the complete graph are colored black or white.

   **Lemma:** In any complete graph with edges colored using 2 colors, at least one color induces a graph whose diameter is at most 3.

   Intuition:
   - For 4 vertices, in *any* 2-edge-coloring, at least one color graph is connected with diameter ≤ 3.
   - For general \(N\), if both color-graphs had a pair of vertices at distance > 3, looking at the 4 involved vertices leads to a contradiction with the 4-vertex case.

   Consequence: with 2 colors, you can always pick one color and its edges alone give distance ≤ 3 between every pair of vertices.

3. **Reduce M colors to 2 via parity**

   Companies are numbered \(1..M\). Partition them by parity:
   - Even: \(2,4,\dots\)
   - Odd: \(1,3,\dots\)

   For each edge, consider `c(i,j) % 2`:
   - 0 → “even company group”
   - 1 → “odd company group”

   This yields a 2-coloring of the edges: “even” vs “odd”.

   By the lemma, **either all-even edges or all-odd edges form a graph of diameter ≤ 3**.

4. **Antitrust limit matches parity group size**

   Number of odd indices in `1..M`:
   \[
   \#\text{odd} = \left\lceil \frac{M}{2} \right\rceil
   \]

   Number of even indices in `1..M`:
   \[
   \#\text{even} = \left\lfloor \frac{M}{2} \right\rfloor
   \]

   Allowed number of companies:
   \[
   L = \left\lfloor \frac{M+1}{2} \right\rfloor = \left\lceil \frac{M}{2} \right\rceil
   \]

   Therefore:
   - The odd group size is exactly \(L\).
   - The even group size is ≤ \(L\).

   So:
   - Buying all odd companies always respects the limit.
   - Buying all even companies also respects the limit.

5. **We only need to test which parity works**

   From the lemma:
   - At least one of “all-even edges” or “all-odd edges” has diameter ≤ 3.
   - So algorithm:
     - Test if even edges alone yield diameter ≤ 3.
     - If yes → buy all even companies.
     - If no → buy all odd companies (must work by lemma).

   We never need to print `-1`: a valid solution always exists.

6. **How to test a parity: Floyd–Warshall**

   For a given parity (say even edges):

   - Create a distance matrix `dist[i][j]`:
     - 0 if `i == j`
     - 1 if edge `i-j` is of that parity
     - INF otherwise
   - Run Floyd–Warshall to compute all-pairs shortest paths.
   - Check all pairs `(i,j)`:
     - If any `dist[i][j] > 3`, that parity fails.
     - Else that parity is good.

   Complexity:
   - \(N \le 200\).
   - Floyd–Warshall: \(O(N^3) \approx 8 \cdot 10^6\) operations → OK.

---

3. **Full solution approach**

1. **Read input**: `N`, `M`, and an `N × N` matrix `A`.
   - `A[i][i] = 0`.
   - `A[i][j]` (for `i != j`) is the company index for flight `i <-> j`.
     Graph is undirected: `A[i][j] == A[j][i]`.

2. **Compress colors to parity**

   Replace each `A[i][j]` by `A[i][j] % 2`:
   - `0` → even.
   - `1` → odd.

3. **Check whether even parity alone works**

   Build `dist` as:

   - `dist[i][i] = 0` for all `i`.
   - For `i != j`:
     - If `A[i][j] == 0` (even), set `dist[i][j] = 1`.
     - Else set `dist[i][j] = INF`.

   Run Floyd–Warshall:

   ```text
   for k in 0..N-1:
     for i in 0..N-1:
       for j in 0..N-1:
         dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
   ```

   Afterward:
   - If any `dist[i][j] > 3`, then “even” fails.
   - Else “even” is good.

4. **Choose companies**

   - If “even” works:
     - Buy all even company indices: 2, 4, 6, ..., ≤ M.
   - Otherwise:
     - Buy all odd company indices: 1, 3, 5, ..., ≤ M.

   This always respects the limit \(L = \lfloor (M+1)/2\rfloor\).

5. **Output**

   - First line: count of chosen companies.
   - Second line: their indices in any order.

   A solution always exists (by the 2-color lemma), so we never need to output `-1` in practice, even though the statement allows that possibility.

---

4. **C++ implementation with detailed comments**

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

// We use some small helpers to read/print vectors nicely.
// (This is not necessary but makes the code a bit shorter.)

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for (auto &x : a) in >> x;
    return in;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for (auto x : a) out << x << ' ';
    return out;
}

// Global variables for convenience
int n, m;
vector<vector<int>> G;   // adjacency matrix: company index (later: parity)

void read_input() {
    cin >> n >> m;
    G.assign(n, vector<int>(n, 0));
    cin >> G;  // uses overloaded operator>>
}

// Check if using ONLY edges of even parity (company index % 2 == 0)
// yields diameter <= 3.
bool even_parity_works() {
    const int INF = (int)1e9;

    // dist[i][j] = shortest number of even edges needed to go from i to j
    vector<vector<int>> dist(n, vector<int>(n, INF));

    // Distance from a node to itself is 0
    for (int i = 0; i < n; ++i)
        dist[i][i] = 0;

    // Direct edges of even parity have cost 1.
    // Note: G already stores parity (after we do G[i][j] %= 2 in solve()).
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (G[i][j] == 0) {       // even parity edge
                dist[i][j] = 1;
                dist[j][i] = 1;       // undirected
            }
        }
    }

    // Floyd–Warshall: compute all-pairs shortest path among even edges
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            // Small optimization: skip if i cannot reach k at all
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < n; ++j) {
                if (dist[k][j] == INF) continue;
                int candidate = dist[i][k] + dist[k][j];
                if (candidate < dist[i][j])
                    dist[i][j] = candidate;
            }
        }
    }

    // Check diameter condition: all pairs must be within 3 steps
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist[i][j] > 3) {
                return false;   // some pair too far → even parity not enough
            }
        }
    }
    return true;   // all pairs within 3 steps
}

void solve() {
    // Step 1: reduce company indices to parity: 0 = even, 1 = odd
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            G[i][j] %= 2;

    // Step 2: test if "even" edges alone give diameter <= 3
    bool even_ok = even_parity_works();

    // Step 3: choose companies based on which parity works
    vector<int> answer;

    if (even_ok) {
        // Buy all even indices: 2, 4, 6, ...
        for (int company = 2; company <= m; company += 2)
            answer.push_back(company);
    } else {
        // Even parity failed, so odd must work by the lemma.
        // Buy all odd indices: 1, 3, 5, ...
        for (int company = 1; company <= m; company += 2)
            answer.push_back(company);
    }

    // Step 4: output result
    cout << answer.size() << "\n";
    if (!answer.empty()) {
        cout << answer << "\n";  // uses overloaded operator<< for vectors
    } else {
        // Theoretically this cannot happen for m >= 1,
        // but we handle it for completeness.
        cout << "\n";
    }
}

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

    read_input();
    solve();
    return 0;
}
```

---

5. **Python implementation with detailed comments**

```python
import sys

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)

    # Read N (cities) and M (companies)
    n = int(next(it))
    m = int(next(it))

    # Read adjacency matrix: G[i][j] is company index (0 on diagonal)
    G = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            G[i][j] = int(next(it))

    # Reduce all company indices to parity: 0 = even, 1 = odd
    for i in range(n):
        for j in range(n):
            G[i][j] %= 2

    def even_parity_works():
        """
        Return True if using only edges of even parity (G[i][j] == 0)
        yields a graph of diameter <= 3 among all n cities.
        """
        INF = 10**9

        # dist[i][j] = shortest number of even edges from i to j
        dist = [[INF] * n for _ in range(n)]

        # Distance from vertex to itself is 0
        for i in range(n):
            dist[i][i] = 0

        # Direct even edges have distance 1
        for i in range(n):
            for j in range(i + 1, n):
                if G[i][j] == 0:    # even parity
                    dist[i][j] = 1
                    dist[j][i] = 1  # undirected

        # Floyd–Warshall: all-pairs shortest paths
        for k in range(n):
            dk = dist[k]
            for i in range(n):
                di = dist[i]
                ik = di[k]
                if ik == INF:
                    # If i cannot reach k, no need to use k as intermediate
                    continue
                # Try relaxing distances via vertex k
                for j in range(n):
                    alt = ik + dk[j]
                    if alt < di[j]:
                        di[j] = alt

        # Check diameter condition: all pairs must have distance <= 3
        for i in range(n):
            for j in range(n):
                if dist[i][j] > 3:
                    return False
        return True

    # Decide which parity to use
    even_ok = even_parity_works()

    # Prepare list of companies to buy:
    # - If even_ok is True: buy all even companies (2, 4, ..., <= m)
    # - Else: buy all odd companies (1, 3, 5, ..., <= m)
    ans = []
    if even_ok:
        start = 2
    else:
        start = 1

    for company in range(start, m + 1, 2):
        ans.append(company)

    # Output
    out_lines = []
    out_lines.append(str(len(ans)))
    if ans:
        out_lines.append(" ".join(map(str, ans)))
    else:
        # Practically won't happen (since m >= 1), but be robust.
        out_lines.append("")

    sys.stdout.write("\n".join(out_lines))

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

This completes a step-by-step, parity-based solution that is guaranteed to find a valid set of companies and respects the purchase limit.