p530.ans1
======================
1

=================
p530.in1
======================
4 3
1 4
2 4
3 4

=================
p530.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;
};

const int inf = (int)1e9 + 42;

int n, m;
vector<vector<int>> adj;

void read() {
    cin >> n >> m;
    adj.assign(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);
    }
}

void bfs(int start, vector<vector<int>>& distances, int genius) {
    vector<int> d(n, -1);
    queue<int> q;
    d[start] = 0;
    q.push(start);
    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 i = 0; i < n; i++) {
        distances[i][genius] = (d[i] == -1 ? inf : d[i]);
    }
}

void solve() {
    // This solution determines which company recruits two geniuses by
    // analyzing shortest-path distances from the three geniuses (nodes 0, 1,
    // 2). Both companies optimally start with one genius and expand their
    // connected component. The winner is decided by who seizes the critical
    // "junction" vertices that improve access to the other two geniuses.
    //
    // For each of the 6 permutations of genius roles (which genius is primary):
    //     - Sort nodes by increasing distance from the primary (then secondary,
    //       then tertiary as tiebreakers).
    //     - Sweep layer by layer. This simulates the natural order in which
    //       nodes become reachable during alternating hiring turns.
    //     - Maintain the best (minimum) remaining distances to the two target
    //       geniuses seen so far, plus a set of seen (dist_b, dist_c) pairs.
    //     - A node is dominated if it offers no improvement over the current
    //       best distances or its exact pair was already encountered earlier.
    //
    // In other words, the dominated vertices can be though of vertices where
    // there exists some "intersection" that's strictly better. Essentially, if
    // at some point first company occupies a dominated intersection, the second
    // company can occupy (or start), from the one that's strictly better (in at
    // least 2 components). If any node survives undominated across all six
    // orderings, it is an unstealable strategic point that Company 1 can always
    // reach first, allowing it to secure two geniuses regardless of opening
    // moves. Otherwise every node is stealable in at least one scenario, so
    // Company 2 wins with perfect play.

    vector<vector<int>> distances(n, vector<int>(3));
    for(int i = 0; i < 3; i++) {
        bfs(i, distances, i);
    }

    vector<int> nodes(n);
    vector<bool> is_dominated(n, false);
    vector<int> perm = {0, 1, 2};
    iota(nodes.begin(), nodes.end(), 0);

    do {
        int primary = perm[0];
        int secondary = perm[1];
        int tertiary = perm[2];

        sort(nodes.begin(), nodes.end(), [&](int a, int b) {
            for(int k = 0; k < 3; k++) {
                if(distances[a][perm[k]] != distances[b][perm[k]]) {
                    return distances[a][perm[k]] < distances[b][perm[k]];
                }
            }
            return a < b;
        });

        map<pair<int, int>, int> seen;
        int best_sec = inf;
        int best_tert = inf;

        for(int i = 0; i < n;) {
            int layer_start = i;
            int curr_dist = distances[nodes[i]][primary];

            while(i < n && distances[nodes[i]][primary] == curr_dist) {
                int v = nodes[i];
                int db = distances[v][secondary];
                int dc = distances[v][tertiary];

                if(db > best_sec || dc > best_tert || seen.count({db, dc})) {
                    is_dominated[v] = true;
                }
                i++;
            }

            for(int j = layer_start; j < i; j++) {
                int v = nodes[j];
                int db = distances[v][secondary];
                int dc = distances[v][tertiary];
                seen[{db, dc}] = 1;
                best_sec = min(best_sec, db);
                best_tert = min(best_tert, dc);
            }
        }
    } while(next_permutation(perm.begin(), perm.end()));

    bool company_one_wins = false;
    for(bool marked: is_dominated) {
        if(!marked) {
            company_one_wins = true;
            break;
        }
    }

    cout << (company_one_wins ? 1 : 2) << '\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();
        solve();
    }

    return 0;
}

=================
p530.ans2
======================
2

=================
p530.in2
======================
6 6
1 4
1 5
2 5
2 6
3 6
3 4

=================
statement.txt
======================
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.


=================
