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

530. Recruiting
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Hurry! Two well-known software companies are recruiting programmers. Initially the total number of unemployed programmers is n. The companies are hiring them one by one, alternately. In one turn a company hires one of the programmers who has not been hired yet. The first company starts hiring.

Furthermore, there are some pairs of friends among the programmers. Of course, a programmer may have several friends. Friendship is a symmetrical relationship, so if a is a friend of b then b is a friend of a.

All such pairs are known to the companies, and the companies follow the rule: a new programmer hired by a company must have at least one friend among the programmers already working in this company. The only exception is a programmer that a company starts with, he can be chosen arbitrarily. It may happen that after a number of turns a company can not longer hire anyone else according to the rule. In this case it stops hiring, while the other company can continue.

As usual, not all the programmers are created equal. There are three geniuses among them, and each company wants to hire as many geniuses as possible. Note that each company always can guarantee one genius to itself starting with a genius. So the question is, which company will hire two geniuses, if they both use optimal strategies.

Note that both companies have the full information during the hiring: friendship relations, who are geniuses and which programmers were hired by each company in each turn.

Input
The first line of the input contains two integers n and m (3 ≤ n ≤ 105, 2 ≤ m ≤ 2 · 105) — the number of programmers and the number of pairs of friends among them, respectively. The programmers are numbered with integers from 1 to n. The geniuses have numbers 1, 2 and 3. The next m lines decribe pairs of friends. Each line contains a pair of integers ai, bi (1 ≤ ai,bi ≤ n, ai ≠ bi), where ai and bi are friends in the i-th pair. No pair occurs more than once, even in reverse order.

Output
Output the number of the company (1 or 2) which will recruit two geniuses. It is guaranteed that one company will hire two geniuses.

Example(s)
sample input
sample output
4 3
1 4
2 4
3 4
1

sample input
sample output
6 6
1 4
1 5
2 5
2 6
3 6
3 4
2



Note
In the second example, programmers form a symmetric cycle of length 6. If the first company starts with a genius (say, number 1), the second one takes the programmer number 5. Then if the first company recruits the 4-th programmer, the second one recruits the 2-nd genius, and now it is closer to the 3-rd genius. Otherwise, if the first company starts with a usual programmer (say, number 4), the second company takes the 1-st genius and afterwards also wins. The remaining cases are considered symmetrically. In all the cases the second company has a strategy of recruiting two geniuses.

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

You are given an undirected graph of `n` programmers with `m` friendship edges. Two companies hire programmers alternately (Company 1 first).  

- A company may pick **any** programmer as its **first** hire.
- After that, each next hire must be a neighbor (friend) of **someone already hired by that same company**.  
  (So each company’s hired set always stays connected and “expands” from its start.)

Programmers `1,2,3` are geniuses. Both companies play optimally to maximize how many geniuses they get. It’s guaranteed that exactly one company will end up with **two** geniuses. Output `1` or `2`: which company gets two geniuses.

Constraints: `n ≤ 1e5`, `m ≤ 2e5`.

---

## 2) Key observations needed to solve the problem

1. **A company’s expansion is like BFS layers from its start.**  
   If a company starts at node `s`, then the earliest it can possibly hire a node `v` (ignoring the opponent) is its shortest-path distance `dist(s, v)`.

2. **Only distances to the three geniuses matter.**  
   The game outcome depends on how fast each company can reach geniuses and “junction” vertices that help reach the other geniuses.  
   So compute `dist(v, 1)`, `dist(v, 2)`, `dist(v, 3)` for every vertex `v` using **3 BFS** runs.

3. **We test “is there a uniquely strong junction vertex?”**  
   A vertex `v` can be seen as a potential “meeting/junction” point from which it’s good to reach two remaining geniuses.  
   If Company 1 can force getting some vertex that is not “dominated” by any earlier (closer) vertex in the relevant ordering, it can secure an advantage leading to two geniuses.

4. **We must consider all 6 roles of the geniuses.**  
   Depending on play, a company may treat one genius as “primary” (the one it already has / races from), and the other two as “secondary/tertiary” targets.  
   Hence check all permutations `(a,b,c)` of `{1,2,3}`.

5. **Dominance can be checked by sweeping vertices in increasing distance to the primary genius.**  
   For a permutation `(a,b,c)`:
   - sort vertices by `(dist(v,a), dist(v,b), dist(v,c))`
   - sweep by groups with equal `dist(v,a)` (primary-distance “layers”)
   - only vertices in **strictly earlier layers** are guaranteed to be reachable earlier from `a`, so dominance comparisons must only use those.

---

## 3) Full solution approach based on the observations

### Step A: Compute distances from each genius
Run BFS from nodes `1`, `2`, `3` (0-based: `0,1,2`) to compute arrays:
- `D[v][0] = dist(v, genius1)`
- `D[v][1] = dist(v, genius2)`
- `D[v][2] = dist(v, genius3)`
Unreachable distance is treated as `INF`.

Time: `O(n+m)` per BFS ⇒ `O(n+m)` overall up to constants.

---

### Step B: For each permutation `(a,b,c)`, mark “dominated” vertices
For each of the 6 permutations of `(0,1,2)`:

1. **Sort all vertices** by:
   ```
   (D[v][a], D[v][b], D[v][c], v)
   ```

2. **Sweep by layers of equal `D[v][a]`.**  
   Maintain information only from **previous layers** (strictly smaller `D[*][a]`):
   - `best_b` = minimum `D[u][b]` seen so far
   - `best_c` = minimum `D[u][c]` seen so far
   - `seen` = set of pairs `(D[u][b], D[u][c])` seen so far

3. For every vertex `v` in the current layer, declare it **dominated** in this permutation if **any** holds:
   - `D[v][b] > best_b`  (someone earlier is strictly better for reaching `b`)
   - `D[v][c] > best_c`  (someone earlier is strictly better for reaching `c`)
   - `(D[v][b], D[v][c])` is already in `seen` (an earlier layer has an equivalent pair)

4. After classifying the entire layer, **add the layer to history**:
   update `best_b`, `best_c`, and insert all `(D[v][b], D[v][c])` into `seen`.

We keep a global boolean `dominated[v]` meaning:  
“`v` was dominated in **at least one** permutation.”

---

### Step C: Decide the winner
- If there exists a vertex `v` such that `dominated[v] == false` (never dominated in any permutation), then **Company 1** can force the win ⇒ output `1`.
- Otherwise output `2`.

This is exactly what the reference solutions do.

---

### Complexity
- 3 BFS: `O(n+m)`
- For 6 permutations: sorting `n` vertices each time: `O(6 * n log n)`
- Sweeps: `O(6 * n)` plus set operations.

Fits comfortably in limits.

---

## 4) C++ implementation with detailed comments

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

static const int INF = (int)1e9 + 42;

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

    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // distances[v][k] = shortest distance from vertex v to genius k (k=0,1,2)
    vector<array<int,3>> distances(n);

    // BFS from a given source genius
    auto bfs = [&](int src, int k) {
        vector<int> d(n, -1);
        queue<int> q;
        d[src] = 0;
        q.push(src);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (d[v] == -1) {
                    d[v] = d[u] + 1;
                    q.push(v);
                }
            }
        }
        for (int v = 0; v < n; v++) {
            distances[v][k] = (d[v] == -1 ? INF : d[v]);
        }
    };

    // Geniuses are 1,2,3 -> 0,1,2 in 0-based
    for (int k = 0; k < 3; k++) bfs(k, k);

    vector<int> nodes(n);
    iota(nodes.begin(), nodes.end(), 0);

    // dominated[v] = true if v is dominated in at least one permutation sweep
    vector<char> dominated(n, 0);

    vector<int> perm = {0, 1, 2};
    do {
        int a = perm[0]; // primary genius
        int b = perm[1]; // secondary
        int c = perm[2]; // tertiary

        // Sort by (dist to a, then b, then c, then id)
        sort(nodes.begin(), nodes.end(), [&](int x, int y) {
            if (distances[x][a] != distances[y][a]) return distances[x][a] < distances[y][a];
            if (distances[x][b] != distances[y][b]) return distances[x][b] < distances[y][b];
            if (distances[x][c] != distances[y][c]) return distances[x][c] < distances[y][c];
            return x < y;
        });

        // We only allow "history" from strictly smaller dist-to-a layers.
        int best_b = INF;
        int best_c = INF;

        // Track seen pairs (dist-to-b, dist-to-c) from previous layers.
        // map is fine; unordered_set with custom hash also works.
        map<pair<int,int>, int> seen;

        // Sweep layer-by-layer on distance to a
        for (int i = 0; i < n; ) {
            int layer_start = i;
            int layer_dist_a = distances[nodes[i]][a];

            // 1) classify nodes in this layer using only previous layers' info
            while (i < n && distances[nodes[i]][a] == layer_dist_a) {
                int v = nodes[i];
                int db = distances[v][b];
                int dc = distances[v][c];

                // Dominated if worse in b or c than previous best, or same pair already existed.
                if (db > best_b || dc > best_c || seen.count({db, dc})) {
                    dominated[v] = 1;
                }
                i++;
            }

            // 2) commit this entire layer into history
            for (int j = layer_start; j < i; j++) {
                int v = nodes[j];
                int db = distances[v][b];
                int dc = distances[v][c];
                seen[{db, dc}] = 1;
                best_b = min(best_b, db);
                best_c = min(best_c, dc);
            }
        }

    } while (next_permutation(perm.begin(), perm.end()));

    // If any vertex is never dominated in any permutation, company 1 wins.
    bool company1 = false;
    for (int v = 0; v < n; v++) {
        if (!dominated[v]) {
            company1 = true;
            break;
        }
    }

    cout << (company1 ? 1 : 2) << "\n";
    return 0;
}
```

---

## 5) Python implementation with detailed comments

```python
import sys
from collections import deque

INF = 10**18

def bfs(start: int, adj, n: int):
    """Return distances from start; unreachable => INF."""
    dist = [-1] * n
    q = deque([start])
    dist[start] = 0
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return [INF if x == -1 else x for x in dist]

def solve():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        adj[u].append(v)
        adj[v].append(u)

    # Distances to geniuses 0,1,2 (originally 1,2,3)
    d0 = bfs(0, adj, n)
    d1 = bfs(1, adj, n)
    d2 = bfs(2, adj, n)

    # dist_vk[v] = (dist to g0, dist to g1, dist to g2)
    dist_vk = list(zip(d0, d1, d2))

    nodes = list(range(n))
    dominated = [False] * n

    perms = [
        (0, 1, 2), (0, 2, 1),
        (1, 0, 2), (1, 2, 0),
        (2, 0, 1), (2, 1, 0),
    ]

    for a, b, c in perms:
        # Sort by (dist to a, then b, then c, then id)
        nodes.sort(key=lambda v: (dist_vk[v][a], dist_vk[v][b], dist_vk[v][c], v))

        best_b = INF
        best_c = INF
        seen = set()  # pairs (dist to b, dist to c) from earlier a-layers

        i = 0
        while i < n:
            layer_start = i
            layer_da = dist_vk[nodes[i]][a]

            # classify within the layer using only previous layers
            while i < n and dist_vk[nodes[i]][a] == layer_da:
                v = nodes[i]
                db = dist_vk[v][b]
                dc = dist_vk[v][c]
                if db > best_b or dc > best_c or (db, dc) in seen:
                    dominated[v] = True
                i += 1

            # commit layer into history
            for j in range(layer_start, i):
                v = nodes[j]
                db = dist_vk[v][b]
                dc = dist_vk[v][c]
                seen.add((db, dc))
                if db < best_b:
                    best_b = db
                if dc < best_c:
                    best_c = dc

    # If any node is never dominated, company 1 wins; else company 2.
    print(1 if any(not x for x in dominated) else 2)

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

If you want, I can also add an intuitive “game interpretation” of why the dominance condition corresponds to optimal counter-strategies (it’s the key non-obvious part), but the above matches the accepted editorial approach.