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

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

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;
};

int n, k;
vector<vector<int>> G;

void read() {
    cin >> n >> k;
    G.assign(n, vector<int>(n, 0));
    cin >> G;
}

bool solve_even() {
    vector<vector<int>> dist(n, vector<int>(n, (int)1e9));
    for(int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(G[i][j] == 0) {
                dist[i][j] = 1;
                dist[j][i] = 1;
            }
        }
    }

    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(dist[i][j] > 3) {
                return false;
            }
        }
    }
    return true;
}

void solve() {
    // In problems like this, it's always good to ask the question of when this
    // is actually possible. Turns out it always is. In particular, let's
    // consider the case of only 2 colours, as reducing k colours to that case
    // is trivial - just split into "odd" and "even" colours.
    //
    // The claim is that for 2 colours, one of them always satisfies that the
    // distance between each pair is <= 3. Let's consider the case of n=4 first.
    // We can go through all examples to convince ourselves, but there is a
    // simpler argument for why this is true - for any graph G, either G or K_n
    // - G is connected (this is a standard results which we can get convinced
    // about by thinking about the complementary edges and that they connect all
    // connected components in G), and with n nodes the distance is always <= 3
    // (as 4 edges means a cycle and so not a simple path).
    //
    // Now let's look at n > 4 and assume for contradiction. This means that for
    // both colours, there are 2 vertices (u_black, v_black) and (u_white,
    // v_white) such that the black distance between u_black and v_black is > 3,
    // and the white distance between u_white and v_white is > 3. However, we
    // already have a result for n = 4: consider the subgraph with V = {u_black,
    // v_black, u_white, v_black} and the result implying that there is at least
    // one colour that has distance less than or equal to 3 between all pairs.
    // This means there is a trivial contradiction between one of the two
    // assumptions.
    //
    // Now that we have some results, let's actually solve the problem. The
    // first step is to split the K colours into 2. This will be done via the
    // parity. Afterwards, we can just do Floyd to check if all distances are
    // less than or equal to 3, as the constraints are n <= 200. We should
    // technically be able to do this a bit faster with bitsets - it's enought
    // to compute G^1, G^2 and G^3, but for this problem Floyd is enough.

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            G[i][j] = G[i][j] % 2;
        }
    }

    vector<int> ans;
    for(int i = 1 + solve_even(); i <= k; i += 2) {
        ans.push_back(i);
    }

    cout << ans.size() << endl;
    cout << ans << endl;
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        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.