#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <random>
#include <string>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <bitset>
#include <array>
#include <stack>
#include <sstream>
using namespace std;
typedef long long ll;
 
string to_string(string a) { return '"' + a + '"'; }
string to_string(char a) { return "'" + string(1, a) + "'"; }
string to_string(const char* a) { return to_string((string) a); }
string to_string(bool a) { return a ? "true" : "false"; }
template <class T1, class T2>
string to_string(pair<T1, T2> a) {
    return "(" + to_string(a.first) + ", " + to_string(a.second) + ")";
}
template <class T>
string to_string(T a) {
    bool first = true; string res = "{";
    for (const auto& i : a) {
        if (!first) res += ", ";
        first = false;
        res += to_string(i);
    }
    res += "}";
    return res;
}
void debug_out() { cerr << endl; }
template <class T1, class... T2>
void debug_out(T1 a, T2... b) {
    cerr << " " << to_string(a);
    debug_out(b...);
}
 
#ifdef LOCAL
#define out(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define out(...) 42
#endif

clock_t start_time; void start_timer() { start_time = clock(); }
double get_time() { return (double) (clock() - start_time) / CLOCKS_PER_SEC; }

void Solve();

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("usr/share/man/man1/input.txt", "r", stdin);
#endif
    start_timer();
    Solve();
#ifdef LOCAL
    cerr << fixed << setprecision(3);
    cerr << endl << "Time spent: " << get_time() << endl;
#endif
    return 0;
}

// do something, stay focused
// look for stupid bugs
// guess, slow, stress
// don't overgeneralize
// don't rush

// don't waste time on standings

// SOLVE THE PROBLEM OR DIE TRYING
// THE SOLUTION IS ALWAYS SIMPLE
// THE CODE IS ALWAYS SHORT

const int N = 1005; // edges
const int K = 1005; // vertices / colors

struct Edge {
    int u, v;
};

struct Elem {
    int color;
    Edge edge;
    bool in_set = 0;
    int set_pos;
    int par;
};

vector<Elem> ground;
vector<int> indep;

struct GraphMatroid {
    struct Graph {
        vector<Edge> es;
        int par[K];
        int dep[K];
        int find(int v) {
            if (par[v] == v) return v;
            return par[v] = find(par[v]);
        }
        void unite(int u, int v) {
            u = find(u);
            v = find(v);
            if (u == v) return;
            if (dep[u] < dep[v]) swap(u, v);
            par[v] = u;
            if (dep[u] == dep[v]) dep[u]++;
        }
        void add_edge(Edge e) {
            es.push_back(e);
        }
        void reset() {
            es.clear();
        }
        int size() {
            return (int) es.size();
        }
        void build_dsu() {
            for (int i = 0; i < K; i++) {
                par[i] = i;
                dep[i] = 0;
            }
            for (Edge e : es) {
                unite(e.u, e.v);
            }
        }
        bool indep_with(Edge e) {
            return find(e.u) != find(e.v);
        }
    };
    Graph basis;
    Graph basis_without[K];
    bool oracle(int add) {
        return basis.indep_with(ground[add].edge);
    }
    bool oracle(int add, int rem) {
        int id = ground[rem].set_pos;
        return basis_without[id].indep_with(ground[add].edge);
    }
    void init() {
        basis.reset();
        for (int i = 0; i < indep.size(); i++) {
            basis_without[i].reset();
        }
        for (int i = 0; i < indep.size(); i++) {
            basis.add_edge(ground[indep[i]].edge);
            for (int j = 0; j < indep.size(); j++) {
                if (j != i) {
                    basis_without[j].add_edge(ground[indep[i]].edge);
                }
            }
        }
        basis.build_dsu();
        for (int i = 0; i < indep.size(); i++) {
            basis_without[i].build_dsu();
        }
    }
};

struct ColorfulMatroid {
    bool used[K];
    bool oracle(int add) {
        return !used[ground[add].color];
    }
    bool oracle(int add, int rem) {
        int add_col = ground[add].color;
        int rem_col = ground[rem].color;
        if (!used[add_col]) return 1;
        return add_col == rem_col;
    }
    void init() {
        for (int i = 0; i < K; i++) {
            used[i] = 0;
        }
        for (int i : indep) {
            used[ground[i].color] = 1;
        }
    }
};

GraphMatroid graph;
ColorfulMatroid color;

bool augment() {
    static const int kSource = -1;
    static const int kNotVisited = -2;
    static const int kNotFound = -3;
    graph.init();
    color.init();
    for (int i = 0; i < ground.size(); i++) {
        ground[i].par = kNotVisited;
    }
    int id = kNotFound;
    queue<int> q;
    for (int i = 0; i < ground.size(); i++) {
        if (color.oracle(i)) {
            ground[i].par = kSource;
            q.push(i);
        }
    }
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (ground[cur].in_set) {
            for (int to = 0; to < ground.size(); to++) {
                if (ground[to].par != kNotVisited) continue;
                if (!color.oracle(to, cur)) continue;
                ground[to].par = cur;
                q.push(to);
            }
            continue;
        }
        if (graph.oracle(cur)) {
            id = cur;
            break;
        }
        for (int to : indep) {
            if (ground[to].par != kNotVisited) continue;
            if (!graph.oracle(cur, to)) continue;
            ground[to].par = cur;
            q.push(to);
        }
    }
    if (id == kNotFound) {
        return 0;
    }
    do {
        ground[id].in_set ^= 1;
        id = ground[id].par;
    } while (id != kSource);
    indep.clear();
    for (int i = 0; i < ground.size(); i++) {
        if (!ground[i].in_set) continue;
        ground[i].set_pos = (int) indep.size();
        indep.push_back(i);
    }
    return 1;
}

void add_element(Edge edge, int color) {
    ground.emplace_back();
    ground.back().edge = edge;
    ground.back().color = color;
}

void matroid_intersection() {
    while (augment());
}

vector<Edge> es[N];

void init() {
    ground.clear();
    indep.clear();
}

void Solve() {
    int n, m;
    //cin >> n >> m;
    n = 1000;
    m = n - 1;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        //cin >> u >> v >> w;
        u = i;
        v = i + 1;
        w = i - 1;
        es[w].push_back({u, v});
    }
    if (es[0].empty()) {
        cout << "0\n";
        return;
    }
    for (int w = 0; w <= n + 1; w++) {
        if (n >= 500 && w == n / 2) {
            init();
        }
        for (Edge e : es[w]) {
            add_element(e, w);
        }
        if (!augment()) {
            cout << w << "\n";
            break;
        }
    }
}