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

147. Black-white king
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



On the chessboard of size NxN leaves only three figures. They are black king, white king and black-white king. The black-white king is very unusual chess piece for us, because it is invisible. Black and white kings decided to conclude a treaty against black-white king (they don't see it, but know that it is somewhere near at chessboard). To realize there plans black and white must meet face to face, what means that they must occupy two neighboring cells (generally each cell has 8 neighbors). The black-white king wants to prevent them from meeting. To do this he must intercept one of the kings before they'll meet, that is to attack one of the kings (make a move to it's cell). If the opponent will make a move on the cell of black-white king, nothing will happen (nobody kill anybody). Your task is to find out have the black-white king chances to win or not. Consider that white and black kings choose the one of the shortest ways to meet. Remember, that they don't see the black-white king. The black-white king also has a strategy: he moves in such a way, that none of the parts of his way can be shortened (for example, he cannot move by zigzag).
In the case of positive answer (i.e. if the probability of black-white king to win is nonzero) find the minimal number of moves necessary to probable victory. Otherwise find the minimal total number of moves of black and white kings necessary to meet. Remember the order of moves: white king, black king, and black-white king. Any king can move to any of the 8 adjacent cells.

Input
First line of input data contains the natural number N (2<=N<=10^6). The second line contains two natural numbers P1, Q1 (0<P1,Q1<N+1) - coordinates of black king, third line contains P2, Q2 (0<P2,Q2<N+1) - coordinates of white king, forth line contains P3, Q3 (0<P3,Q3<N+1) - coordinates of black-white king. Positions of all kings are different.

Output
Write to the first line word "YES" if the answer id positive, and "NO" - otherwise. To the second line write a single number - the numerical answer to the task.

Sample test(s)

Input
5
1 1
5 3
2 3

Output
YES
1
Author:	Michael R. Mirzayanov (Special thanks to S. Surganova and D. Arbenina)
Resource:	Phisical Technical Lyceum #1 Trainings
Date:	Fall, 2002

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

We have an \(N \times N\) chessboard (\(2 \le N \le 10^6\)) and three kings:

- Black king at \((x_1, y_1)\)
- White king at \((x_2, y_2)\)
- Invisible “black‑white” king at \((x_3, y_3)\)

Move order in every step:

1. White moves 1 king step (or stays if we think in terms of shortest paths).
2. Black moves 1 king step.
3. Black‑white moves 1 king step.

A king step = move to any of the up to 8 neighboring squares.

Black and white want to come **face to face**: occupy two **neighboring** cells (Chebyshev distance 1) using **some** shortest paths between them.

The black‑white king tries to **intercept**: before black and white become neighbors, it must make a move to a cell currently occupied by one of them. If black/white moves onto black‑white’s cell, nothing happens.

Additional constraints:

- Black and white always move along a shortest path between their initial positions (but there may be many such paths).
- Black‑white also moves along a “non‑detour” shortest path: it never wastes moves (no zigzags that could be shortened).

We must determine:

- If there exists **any** consistent choice of shortest paths (for all three kings) where black‑white manages to intercept before black and white become neighbors:
  - Output:

    ```
    YES
    t
    ```

    where `t` is the **minimum possible number of moves of the black‑white king** until interception.

- Otherwise:
  - Output:

    ```
    NO
    k
    ```

    where `k` is the **minimal number of moves of each visible king** until they become neighbors (i.e. along optimal shortest paths).

Coordinates are 1‑based, all starting positions are distinct.

---

2. Key observations
-------------------

### 2.1 Distance and meeting time of two visible kings

King distance between two squares is the **Chebyshev distance**:

\[
D = \max(|x_1 - x_2|, |y_1 - y_2|)
\]

- This is the **minimum number of moves** for **one** king to move onto the other’s starting square.
- If both kings move towards each other along shortest paths, they can reduce their distance by 1 per “pair” of their moves, and they become **neighbors** (distance 1) after:

\[
\text{moves per king to become neighbors} = D - 1
\]

If black‑white cannot intercept, the answer is:

- `NO`
- `D - 1`

### 2.2 Timing model

Define time step `t` as: the moment black‑white is *about to make* its `t`‑th move.

After `t` full steps:

- White has made `t` moves.
- Black has made `t` moves.
- Black‑white is about to make its `t`‑th move.

Interception can only happen **during** black‑white’s move (it must move into a visible king’s square), so we only need to consider positions at these discrete times `t = 1, 2, 3, ...`.

### 2.3 Black‑white king’s reachable region

Black‑white moves along some shortest (non‑detour) path. That simply means:

- After `t` moves, it cannot be farther than `t` king steps from its start.
- So its possible positions form a **Chebyshev ball** (an axis‑aligned square) of radius `t`:

If it starts at `(cx, cy)` then at time `t`:

\[
cx - t \le x \le cx + t, \quad
cy - t \le y \le cy + t
\]

This is the square `[cx - t, cx + t] × [cy - t, cy + t]`.

### 2.4 Simplifying the black & white motion

Let the visible kings start at `a = (ax, ay)` and `b = (bx, by)`.

Define

\[
dx = |ax - bx|,\quad dy = |ay - by|,\quad D = \max(dx, dy)
\]

We can **swap x and y axes** for all three kings if necessary so that:

\[
dx \ge dy
\]

This doesn’t change distances (board is square) but simplifies geometry: the “main” separation direction is along x.

In this setup:

- Along some shortest paths, visible kings effectively move **monotonically in x** towards each other.
- There exists a shortest‑path meeting strategy where:

  - One king moves right in x every step (or left),  
  - The other moves left in x every step (or right),  
  - And both adjust y within allowed ranges to remain on a shortest path.

We only need to consider **some** shortest paths: if interception is possible for *any* shortest paths they choose, we must output `YES`. So we can assume this monotone‑x model.

Let

```
int x_dir = (bx > ax) ? 1 : -1;
```

- This is the direction along x in which `b` lies relative to `a`.

Then along our chosen family of shortest paths, at time `t`:

- King `a` has x-coordinate `ax + x_dir * t`
- King `b` has x-coordinate `bx - x_dir * t` (or equivalently with `dir = -x_dir`)

### 2.5 Y‑coordinate constraints for visible kings

At time `t`, visible king starting at `(kx, ky)` and targeting opponent `(ox, oy)`:

1. **Speed constraint**: it has made `t` king moves, so in y:

   \[
   ky - t \le y \le ky + t
   \]

2. **Shortest‑path constraint**: they must still be able to end up neighboring after total `D-1` moves each. That restricts the final vertical distance and thus how far y can deviate from the opponent’s y over time.

A nice closed form that captures this for time `t` is:

```
int y_min = max(
    clamp(ky - t, 1, n),
    clamp(oy - D + t, 1, n)
);
int y_max = min(
    clamp(ky + t, 1, n),
    clamp(oy + D - t, 1, n)
);
```

Intuition:

- `ky ± t` = natural vertical reach after t king moves.
- `oy − (D − t)` and `oy + (D − t)` = if total path length is D, and we’ve already used t steps, then we cannot create a vertical gap so large that it can’t be closed in the remaining `D - t` steps.
- `clamp` enforces board bounds.

So at time `t`, each visible king is at:

- A **fixed x** (linear function of t).
- A **vertical segment** `[y_min, y_max]`.

### 2.6 Intersection condition at time t

At time `t`:

- Black‑white occupies some cell in its square:

  ```text
  [x3, x4] = [cx - t, cx + t]
  [y3, y4] = [cy - t, cy + t]
  ```

- A visible king `K` has:

  - Fixed x: `xK = kx + dir * t`
  - Vertical segment `[y_min, y_max]` as above.

We want to know: is there any cell `(xK, y)` at time `t` that the visible king can occupy, **and** which is also in black‑white’s reachable square?

This reduces to **segment–rectangle intersection in 2D** with:

- Segment: `{x = xK} × [y_min, y_max]`
- Rectangle: `[x3, x4] × [y3, y4]`

The check:

1. If `xK < x3` or `xK > x4`: no overlap in x → no interception.

2. If `xK == x3` or `xK == x4` (on left or right border of the square):

   - Intersect if vertical intervals overlap:

     \[
     \max(y\_min, y3) \le \min(y\_max, y4)
     \]

3. If `x3 < xK < x4` (strictly inside x‑range):

   - Intersect if some y is in both `[y_min, y_max]` and `[y3, y4]`.  
   - A simple way: check if `y3` or `y4` lies in `[y_min, y_max]`.

We must do this **for both visible kings** at each time `t`:

- King a moving toward b with `dir = x_dir`.
- King b moving toward a with `dir = -x_dir`.

If either intersects black‑white’s reachable region: interception is possible at time `t`.

### 2.7 Upper bound on t to check

Total Chebyshev distance is `D`. Visible kings need `D - 1` moves each to become neighbors.

The editorial’s key geometric fact (used by the provided solution):

- If black‑white hasn’t managed to intercept by time:

  \[
  \text{max\_steps} = \left\lfloor\frac{D}{2}\right\rfloor - 1,
  \]

  then no new interception opportunities will appear later before they become neighbors.

So we only need to check:

\[
t = 1,2,\dots,\text{max\_steps}
\]

Edge case:

- If `D <= 2` then `max_steps <= 0`, meaning black & white are already too close; black‑white has effectively no time to cut in. Then interception is impossible and we directly output:

  - `NO`
  - `D - 1` moves per visible king to become neighbors (0 or 1).

### 2.8 Complexity

- \(D \le 10^6\) (coordinates ∈ [1, N], N ≤ 10^6).
- We loop `t` from 1 to at most `D/2 - 1` → O(D).
- Each iteration is O(1).
- Total time O(N), memory O(1) — fine for 0.25 seconds in C++ and still feasible in Python with fast I/O.

---

3. Full solution approach
-------------------------

1. **Read input**: `n`, positions of black king `a`, white king `b`, black‑white king `c`.

2. Optionally check: if `c` starts on the same cell as `a` or `b`, then in terms of the given C++ logic, answer is `YES 0` (though statement says starts are distinct, this is a safety check).

3. Compute:

   ```text
   dx = |ax - bx|
   dy = |ay - by|
   ```

4. If `dx < dy`, swap `x` and `y` coordinates for **all three** kings. Now `dx >= dy`.

5. Let:

   ```text
   D = max(dx, dy)
   max_steps = D / 2 - 1    // integer division
   ```

   If `max_steps <= 0`:

   - No opportunity window for black‑white to intercept.
   - Output:

     ```text
     NO
     D - 1
     ```

   and stop.

6. Determine x‑direction:

   ```text
   x_dir = (bx > ax) ? 1 : -1
   ```

7. Define a helper `clamp(v, 1, n)` to keep coordinates inside `[1, n]`.

8. For each `t` from 1 to `max_steps`:

   - Black‑white’s reachable rectangle:

     ```text
     x3 = cx - t
     x4 = cx + t
     y3 = cy - t
     y4 = cy + t
     ```

   - Define a function `check(king, other, dir)`:

     - Let `king = (kx, ky)`, `other = (ox, oy)`.

       - `x = kx + dir * t`
       - `y_min = max(clamp(ky - t), clamp(oy - D + t))`
       - `y_max = min(clamp(ky + t), clamp(oy + D - t))`

     - If `x < x3 or x > x4`: return False.
     - Else if `x == x3 or x == x4`:

       - Return `max(y_min, y3) <= min(y_max, y4)`.

     - Else (x strictly inside):

       - If `y_min <= y3 <= y_max`: return True.
       - If `y_min <= y4 <= y_max`: return True.
       - Else return False.

   - If `check(a, b, x_dir)` or `check(b, a, -x_dir)` is True:

     - Output:

       ```text
       YES
       t
       ```

     - Stop.

9. If the loop ends without interception:

   - Output:

     ```text
     NO
     D - 1
     ```

This solves the problem.

---

4. C++ Solution
---------------

```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;
pair<int, int> a, b, c;

void read() {
    cin >> n;
    cin >> a >> b >> c;
}

void solve() {
    // The solution to this problem is case work. Probably the hardest part is
    // to actually parse what it asks for. Essentially, we want to check if the
    // "black-white" king can intersect the path of the two other kings. The two
    // other kings will always take max(|x1-x2|, |y1-y2|) steps to meet (time is
    // divided by 2 because they make two steps for a single step of the
    // "black-white"). As N isn't large, we can iterate through the steps until
    // we meet. At step T, we can figure out the range of y coordinates that are
    // reachable by the two kings, and see if the "black-white" can be on any of
    // these cells. This solution is in O(N).

    if(a == c || b == c) {
        cout << "YES\n0\n";
        return;
    }

    int dx = abs(a.first - b.first);
    int dy = abs(a.second - b.second);
    if(dx < dy) {
        swap(a.first, a.second);
        swap(b.first, b.second);
        swap(c.first, c.second);
    }

    int D = max(dx, dy);
    int max_steps = D / 2 - 1;
    int x_dir = (b.first > a.first) ? 1 : -1;

    if(max_steps <= 0) {
        cout << "NO\n" << D - 1 << "\n";
        return;
    }

    auto clamp = [](int v, int lo, int hi) { return max(lo, min(hi, v)); };

    for(int t = 1; t <= max_steps; t++) {
        int x3 = c.first - t, x4 = c.first + t;
        int y3 = c.second - t, y4 = c.second + t;

        auto check = [&](pair<int, int> king, pair<int, int> other, int dir) {
            int x = king.first + dir * t;
            int y_min =
                max(clamp(king.second - t, 1, n),
                    clamp(other.second - D + t, 1, n));
            int y_max =
                min(clamp(king.second + t, 1, n),
                    clamp(other.second + D - t, 1, n));

            if(x < x3 || x > x4) {
                return false;
            }
            if(x == x3 || x == x4) {
                return max(y_min, y3) <= min(y_max, y4);
            }
            return (y_min <= y3 && y3 <= y_max) || (y_min <= y4 && y4 <= y_max);
        };

        if(check(a, b, x_dir) || check(b, a, -x_dir)) {
            cout << "YES\n" << t << "\n";
            return;
        }
    }

    cout << "NO\n" << D - 1 << "\n";
}

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
from typing import Tuple

def clamp(v: int, lo: int, hi: int) -> int:
    """Clamp integer v into the inclusive range [lo, hi]."""
    if v < lo:
        return lo
    if v > hi:
        return hi
    return v

def solve_one(n: int,
              a: Tuple[int, int],
              b: Tuple[int, int],
              c: Tuple[int, int]) -> str:
    """
    Solve one instance of the 'Black-white king' problem.

    Parameters:
        n: board size, N (N x N)
        a: (x, y) of black king
        b: (x, y) of white king
        c: (x, y) of black-white king

    Returns:
        Output string with two lines, as required by the problem.
    """
    ax, ay = a
    bx, by = b
    cx, cy = c

    # Optional early check: if black-white king starts on same square (shouldn't happen).
    if (ax, ay) == (cx, cy) or (bx, by) == (cx, cy):
        return "YES\n0\n"

    # Compute dx, dy for the visible kings.
    dx = abs(ax - bx)
    dy = abs(ay - by)

    # Rotate board (swap x and y) if necessary to ensure dx >= dy.
    if dx < dy:
        ax, ay = ay, ax
        bx, by = by, bx
        cx, cy = cy, cx

        dx = abs(ax - bx)
        dy = abs(ay - by)

    # Chebyshev distance between visible kings.
    D = max(dx, dy)

    # Number of black-white steps to check.
    max_steps = D // 2 - 1

    # Direction along x from king a to king b (1: right, -1: left).
    x_dir = 1 if bx > ax else -1

    # If no positive interception window exists, interception is impossible.
    if max_steps <= 0:
        # Minimal number of moves each visible king needs to become neighbors.
        return f"NO\n{D - 1}\n"

    # Loop over possible times t (black-white moves).
    for t in range(1, max_steps + 1):
        # Black-white king's possible region at time t.
        x3 = cx - t
        x4 = cx + t
        y3 = cy - t
        y4 = cy + t

        def check(king_x: int, king_y: int,
                  other_x: int, other_y: int,
                  dir_: int) -> bool:
            """
            Check if the king that starts at (king_x, king_y) and
            moves in x-direction dir_ towards (other_x, other_y)
            can be at a cell reachable by black-white king at time t.
            """
            # x-coordinate after t steps
            x = king_x + dir_ * t

            # y-range after t steps, given:
            # - vertical speed limit: king_y +/- t
            # - shortest-path constraint relative to (other_x, other_y)
            y_min = max(
                clamp(king_y - t, 1, n),
                clamp(other_y - D + t, 1, n)
            )
            y_max = min(
                clamp(king_y + t, 1, n),
                clamp(other_y + D - t, 1, n)
            )

            # If x is outside black-white's x-range, no intersection.
            if x < x3 or x > x4:
                return False

            # If x lies exactly on left/right boundary of black-white's square:
            if x == x3 or x == x4:
                # Intersection if vertical segments overlap.
                return max(y_min, y3) <= min(y_max, y4)

            # Now x3 < x < x4: inside horizontally.
            # Intersection if any overlap in y-interval.
            if y_min <= y3 <= y_max:
                return True
            if y_min <= y4 <= y_max:
                return True
            return False

        # Try intercepting black king a or white king b.
        if check(ax, ay, bx, by, x_dir) or check(bx, by, ax, ay, -x_dir):
            return f"YES\n{t}\n"

    # If we reach here: interception is impossible before they become neighbors.
    return f"NO\n{D - 1}\n"


def main() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)

    n = int(next(it))
    ax, ay = int(next(it)), int(next(it))
    bx, by = int(next(it)), int(next(it))
    cx, cy = int(next(it)), int(next(it))

    ans = solve_one(n, (ax, ay), (bx, by), (cx, cy))
    sys.stdout.write(ans)


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

This Python solution mirrors the C++ logic and should work within constraints if run with a reasonably fast interpreter.