#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int N = 110, M = 2e5 + 10;
const int inf = 0x3f3f3f3f;

int n, m, s, t;
struct Edge {
    int nex, to, val;
} edge[M];
int head[N], tot, d[N], maxflow;
int a[M], b[M];
queue<int> q;

inline void init() {
    tot = 1;
    for(int i = 0; i <= 2 * n; ++i) {
       head[i] = -1;
    }
    for(int i = 0; i <= m; ++i) {
        a[i] = b[i] = 0;
    }
}
inline void add(int from, int to, int val) {
    edge[++tot].to = to; edge[tot].nex = head[from]; edge[tot].val = val; head[from] = tot;
}
inline void read(int x) {
    string tmp; cin >> tmp;
    int flag = 0;
    for(int i = 1; i <= tmp.length(); ++i) {
        if(tmp[i] == ',')   flag = 1;
        if(isdigit(tmp[i]) && !flag) {
            a[x] = a[x] * 10 + tmp[i] - '0';
        } 
        else if(isdigit(tmp[i]) && flag == 1) {
            b[x] = b[x] * 10 + tmp[i] - '0';
        }
    }
    //a[x]++; b[x]++;
}
bool bfs()          //构建分层图
{
    while(!q.empty())   q.pop();
    for(int i = 0; i <= 2 * n; ++i) d[i] = 0;
    q.push(s); d[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i = head[u]; i != -1; i = edge[i].nex){
            int v = edge[i].to;
            if(edge[i].val && !d[v]){
                d[v] = d[u] + 1;
                q.push(v);
                if(v == t)  return 1;
            }
        }
    }
    return 0;
}
int dfs(int u, int flow)      //flow为当前点的总流量
{
    if(u == t)  return flow;
    int rest = flow, k;         //rest为当前点的剩余可行流量
    for(int i = head[u]; i != -1 && rest; i = edge[i].nex){
        int v = edge[i].to;
        if(edge[i].val && d[v] == d[u] + 1){
            k = dfs(v, min(edge[i].val, rest));
            if(k == 0) d[v] = 0;
            edge[i].val -= k;     //更新参残余网络
            edge[i^1].val += k;
            rest -= k;
        }
    }
    return flow - rest;     //从这个点流出的总流量
}
int dinic(int s, int t) {
    int maxflow = 0, flow = 0;
    while(bfs()) {
        while(flow = dfs(s, inf))    maxflow += flow; //分层一次，找多次增广路
    }
    return maxflow;
}

int main()
{
    while(scanf("%d %d", &n, &m)) {
        init();
        if(n == 0 && m == 0) {
            puts("0"); continue;
        }
        else if(n == 0 || n == 1){
            printf("%d\n", n); continue;
        }
        for(int i = 0; i < m; ++i)  read(i);
        int ans = inf;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(i == j)  continue;
                s = i + n, t = j;
                memset(head, -1, sizeof(head)); tot = 1;
                for(int k = 0; k < n; ++k) {
                    if(k != i && k != j) add(k, k + n, 1), add(k + n, k, 0);
                    else add(k, k + n, inf), add(k + n, k, 0);
                }
                for(int k = 0; k < m; ++k) {
                    add(a[k] + n, b[k], inf); add(b[k], a[k] + n, 0);
                    add(b[k] + n, a[k], inf); add(a[k], b[k] + n, 0);
                };
                ans = min(ans, dinic(s, t));
            }
        }
        if(ans == inf)  ans = n;
        printf("%d\n", ans);
    }
    getchar(); getchar();
}

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <iostream>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const int maxn = 1300;      

int n, m, tot;      //tot存离散化后的数值个数
int a[N], b[N];
int num, x = 0;       
int f[maxn][maxn], pos[N];
int vis[N];
vector<int> ne[N];

void init()
{
    for(int i = 1; i <= pos[n]; ++i)
    {
        int maxval = 0, ans = inf;
        for(int j = 1; j <= tot; ++j)   vis[j] = 0;
        for(int j = (i - 1) * num + 1; j <= n; ++j)
        {
            int t = pos[j];
            vis[a[j]]++;
            if(vis[a[j]] > maxval) {
                maxval = vis[a[j]];
                ans = a[j];
            }
            else if(vis[a[j]] == maxval && a[j] < ans) {
                ans = a[j];
            }
            f[i][t] = ans;
        }
    }
}
int calc(int l, int r, int x)
{
    vector<int>::iterator pl = lower_bound(ne[x].begin(), ne[x].end(), l);
    vector<int>::iterator pr = upper_bound(ne[x].begin(), ne[x].end(), r);
    return pr - pl;
}
int query(int le, int ri)
{
    int l = pos[le], r = pos[ri];
    int ans = f[l+1][r-1];
    int maxv = calc(le, ri, ans);
    for(int i = le; i <= min(ri, l * num); ++i)
    {
        int now = calc(le, ri, a[i]);
        if(now > maxv) {
            ans = a[i];
            maxv = now;
        }
        else if(now == maxv && a[i] < ans)    ans = a[i];
    }
    if(l == r)  return ans;
    for(int i = (r - 1) * num + 1; i <= ri; ++i){
        int now = calc(le, ri, a[i]);
        if(now > maxv) {
            maxv = now;
            ans = a[i];
        }
        else if(now == maxv && a[i] < ans)    ans = a[i];
    }
    return ans;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    tot = unique(b + 1, b + n + 1) - b - 1;
    //debug(tot);
    for(int i = 1; i <= n; ++i) {
        a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
        ne[a[i]].push_back(i);
    }
    num = max(1, (int)(n / sqrt(m * log2(n))));
    for(int i = 1; i <= n; ++i) {
        pos[i] = (i - 1) / num + 1;
    }
    init();
    for(int cas = 1; cas <= m; ++cas)
    {
        int l, r; scanf("%d %d", &l, &r);
        l = (l + x - 1) % n + 1;
        r = (r + x - 1) % n + 1;
        if(l > r)   swap(l, r);
        x = b[query(l, r)];
        printf("%d\n", x);
    }
    getchar(); getchar();
}

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);

struct node{
    int nex, to;
}Edge[maxn<<1];
int tot, head[maxn];
int n, m;
int st[maxn], top, vis[maxn];
int t, ans[maxn];

inline void add(int from, int to){
    Edge[++tot].to = to;
    Edge[tot].nex = head[from];
    head[from] = tot;
}
void euler()
{
    st[++top] = 1;
    while(top > 0){
        int u = st[top], i = head[u];
        while(i != -1 && vis[i])    i = Edge[i].nex;
        if(i != -1){
            int v = Edge[i].to;
            st[++top] = v;
            vis[i] = 1;
            head[u] = Edge[i].nex;
        }
        else{
            top--;
            ans[++t] = u;
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= m; ++i){
        int a, b; cin >> a >> b;
        add(a, b); add(b, a);
    }
    euler();
    for(int i = t; i > 0; --i){
        printf("%d\n", ans[i]);
    }
    getchar(); getchar();
}

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 1100, maxm = 1e6;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);

int n, m, hate[maxn][maxn];
struct node{
    int nex, to;
}Edge[maxm<<1];
int head[maxn], tot;
int dfn[maxn], low[maxn], num, cut[maxn];
vector<int> dcc[maxn];
int ok[maxn], co[maxn], id[maxn];
int root, cnt, flag;
int st[maxn], top;  //数组模拟的栈

inline void init()
{
    cnt = num = 0; tot = 1;
    top = 0;
    for(int i = 1; i <= n; ++i){
        dcc[i].clear();
        dfn[i] = low[i] = cut[i] = 0;
        ok[i] = 0;
        cut[i] = id[i] = 0;
        co[i] = 0;
        for(int j = 1; j <= n; ++j){
            hate[i][j] = 0;
        }
    }
    memset(head, -1, sizeof(head));
}
inline void add(int from, int to){
    Edge[++tot].to = to;
    Edge[tot].nex = head[from];
    head[from] = tot;
}
void tarjan(int u)
{   
    dfn[u] = low[u] = ++num;
    st[++top] = u;
    if(u == root && head[u] == -1){         //是孤立点则是一个单独的连通分量
        dcc[++cnt].push_back(u);
        return;
    }
    int flag = 0;
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]){
                flag++;
                if(flag > 1 || root != u) cut[v] = 1;
                int tmp = st[top];
                cnt++;
                do{
                    tmp = st[top--];
                    dcc[cnt].push_back(tmp);
                } while(tmp != v);
                dcc[cnt].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}
void dfs(int u, int x)
{
    co[u] = x;
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        if(id[u] != id[v])  continue;
        if(!co[v])  dfs(v, 3 - x);
        else if(co[u] == co[v]){
            flag = 1;
            return;
        }
    }
}

int main()
{
    while(~scanf("%d %d", &n, &m), n && m){
        init();
        for(int i = 1; i <= m; ++i){
            int a, b;
            scanf("%d %d", &a, &b);
            hate[a][b] = hate[b][a] = 1;
        }
        for(int i = 1; i <= n; ++i){
            for(int j = i + 1; j <= n; ++j){
                if(hate[i][j])  continue;
                add(i, j);  add(j, i);
            }
        }
        for(int i = 1; i <= n; ++i){
            if(!dfn[i]) root = i, tarjan(i);
        }
        //debug(cnt);
        /* for(int i = 1; i <= cnt; ++i){
            debug(i);
            for(auto x : dcc[i])    printf("%d ", x);
            puts("");
        } */
        int ans = 0;
        for(int i = 1; i <= cnt; ++i){
            for(vector<int>::size_type j = 0; j < dcc[i].size(); ++j){
                id[dcc[i][j]] = i; 
                co[dcc[i][j]] = 0;
            }
            flag = 0;
            dfs(dcc[i][0], 1);
            if(flag){
                for(vector<int>::size_type j = 0; j < dcc[i].size(); ++j){
                    ok[dcc[i][j]] = 1; 
                }
            }  
        }
        for(int i = 1; i <= n; ++i){
            if(!ok[i]) ans++;
            //if(!ok[i])  debug(i);
        }
        printf("%d\n", ans);
    }
    getchar(); getchar();
}

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);

int n, m, t;
int tot, tot2, head[maxn], head2[maxn], dfn[maxn], low[maxn];
struct node{
    int nex, to;
}Edge[maxn], Edge2[maxn];
int num, dcc, id[maxn], bridge[maxn];
int fa[maxn], f[maxn][20], dep[maxn];

inline void init()
{
    tot = tot2 = 1;
    num = dcc = 0;
    for(int i = 1; i <= n; ++i){
        head[i] = head2[i] = -1;
        dfn[i] = low[i] = 0;
        id[i] = 0; fa[i] = i;
        dep[i] = 0;
    }
    memset(bridge, 0, sizeof(bridge));
    memset(f, 0, sizeof(f));
}
int ffind(int x){
    return x == fa[x] ? x : fa[x] = ffind(fa[x]);
}
inline void add(int from, int to){
    Edge[++tot].to = to;
    Edge[tot].nex = head[from];
    head[from] = tot;
}
inline void add2(int from, int to){
    Edge2[++tot2].to = to;
    Edge2[tot2].nex = head2[from];
    head2[from] = tot2;
}
void tarjan(int u, int e)
{
    dfn[u] = low[u] = ++num;
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        if(!dfn[v]){
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]){
                bridge[i] = bridge[i^1] = 1;
            }
        }
        else if(e != (i ^ 1)) low[u] = min(low[u], dfn[v]);
    }
}
void dfs(int u)
{
    id[u] = dcc;
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        if(id[v] || bridge[i])  continue;
        dfs(v);
    }
}
queue<int> q;
void bfs()
{
    while(!q.empty())   q.pop();
    dep[1] = 1; q.push(1);
    while(!q.empty()){
        //cout << 1 << endl;
        int u = q.front(); q.pop();
        for(int i = head2[u]; i != -1; i = Edge2[i].nex){
            int v = Edge2[i].to;
            if(dep[v])  continue;
            dep[v] = dep[u] + 1;
            f[v][0] = u;
            for(int j = 1; j < 20; ++j){
                f[v][j] = f[f[v][j-1]][j-1];
            }
            q.push(v);
        }
    }
}
int lca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 19; i >= 0; --i){
        if(dep[f[u][i]] >= dep[v]) u = f[u][i];
    }
    if(u == v)  return u;
    for(int i = 19; i >= 0; --i){
        if(f[u][i] != f[v][i]){
            u = f[u][i]; v = f[v][i];
        }
    }
    return f[u][0];
}

int main()
{
    int cas = 0;
    while(scanf("%d %d", &n, &m), n && m)
    {
        init();
        for(int i = 1; i <= m; ++i){
            int a, b; 
            scanf("%d %d", &a, &b);
            add(a, b); add(b, a);
        }
        for(int i = 1; i <= n; ++i){
            if(dfn[i])  continue;
            tarjan(i, 0);
        }
        for(int i = 1; i <= n; ++i){
            if(id[i])   continue;
            dcc++; dfs(i);
        }
        for(int i = 2; i < tot; i += 2){
            int u = Edge[i].to, v = Edge[i^1].to;
            if(id[u] == id[v])  continue;
            add2(id[u], id[v]); add2(id[v], id[u]);
        }
        bfs();
        int ans = dcc - 1;
        //debug(ans);
        scanf("%d", &t);
        printf("Case %d:\n", ++cas);
        while(t--){
            int a, b;
            scanf("%d %d", &a, &b);
            a = id[a]; b = id[b];
            a = ffind(a), b = ffind(b);
            int p = lca(a, b);
            //debug(dep[a]); debug(dep[b]); debug(dep[p]);
            while(dep[a] > dep[p]){
                ans--;
                fa[a] = f[a][0];
                a = ffind(a);
            }
            while(dep[b] > dep[p]){
                ans--;
                fa[b] = f[b][0];
                b = ffind(b);
            }
            printf("%d\n", ans);
        }
        puts("");
    }
    getchar(); getchar();
}

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 5e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);

int n, m;
int head[maxn], tot, cut[maxn], num;
struct node{
    int nex, to;
}Edge[maxn<<1];
int dfn[maxn], low[maxn], root, vis[maxn];
LL ans[maxn], sz[maxn];

inline void add(int from, int to){
    Edge[++tot].to = to; Edge[tot].nex = head[from]; head[from] = tot;
}
void tarjan(int u)
{
    low[u] = dfn[u] = ++num;
    int flag = 0;
    sz[u] = 1;
    LL sum = 0;
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            sz[u] += sz[v];
            low[u] = min(low[u], low[v]);
            if(dfn[u] <= low[v]){
                flag++;
                sum += sz[v];
                ans[u] += (n - sz[v]) * sz[v];
                if(flag > 1 || root != u)   cut[u] = 1;
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
    if(!cut[u])  ans[u] = 2 * n - 2;
    else    ans[u] += (n - sum - 1) * (sum + 1) + n - 1;
}
void dfs(int u)
{
    vis[u] = 1;
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        if(vis[v])  continue;
        dfs(v);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    tot = 1;
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= m; ++i){
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b); add(b, a);
    }
    for(int i = 1; i <= n; ++i){
        if(!dfn[i]) root = i, tarjan(i);
    }
    for(int i = 1; i <= n; ++i){
        printf("%lld\n", ans[i]);
    }   
    getchar(); getchar();
}

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);

int n, m, k;
int tot, head[maxn], dis[maxn], vis[maxn];
struct node{
    int nex, to, val;
}Edge[maxn<<1];
struct Node{
    int dis, pos;
    Node(int dis = 0, int pos = 0) : dis(dis), pos(pos) {}
    friend bool operator <(const Node &a, const Node &b){
        return a.dis > b.dis;
    }
};
priority_queue<Node> q;

void dijkstra(int s)
{
    memset(dis, inf, sizeof(dis));
    dis[s] = 0;
    q.push(Node(0, s));
    while(!q.empty()){
        int u = q.top().pos; q.pop();
        if(vis[u])  continue;
        vis[u] = 1;
        for(int i = head[u]; i != -1; i = Edge[i].nex){
            int v = Edge[i].to, tmp = max(dis[u], Edge[i].val);
            if(dis[v] > tmp){
                dis[v] = tmp;
                q.push(Node(tmp, v));
            }
        }
    }
}
inline void add(int from, int to, int val){
    Edge[++tot].to = to;
    Edge[tot].val = val;
    Edge[tot].nex = head[from];
    head[from] = tot;
}


int main()
{
    scanf("%d %d %d", &n, &m, &k);
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= m; ++i){
        int a, b, val;
        scanf("%d %d %d", &a, &b, &val);
        add(a, b, val); add(b, a, val);
        for(int j = 1; j <= k; ++j){
            add(a + (j - 1) * n, b + j * n, 0);
            add(b + (j - 1) * n, a + j * n, 0);
            add(a + n * j, b + n * j, val);
            add(b + j * n, a + j * n, val);
        }
    }
    for(int i = 1; i <= k; ++i){
        add(i * n, (i + 1) * n, 0);
    }
    dijkstra(1);
    dis[(k + 1) * n] == inf ? puts("-1") : printf("%d\n", dis[(k + 1) * n]);
    getchar(); getchar();
}

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 5e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);

int n, m;
LL arr[maxn];
struct Tree{
    int l, r;
    LL maxv, lsum, rsum, sum;
}t[maxn<<2];

inline LL max(LL a, LL b, LL c){
    return max(a, max(b, c));
}
inline void pushup(int cur){
    t[cur].sum = t[cur<<1].sum + t[cur<<1|1].sum;
    t[cur].lsum = max(t[cur<<1].lsum, t[cur<<1].sum + t[cur<<1|1].lsum);
    t[cur].rsum = max(t[cur<<1|1].rsum, t[cur<<1].rsum + t[cur<<1|1].sum);
    t[cur].maxv = max(t[cur<<1].maxv, t[cur<<1|1].maxv, t[cur<<1].rsum + t[cur<<1|1].lsum);
}
void build(int l, int r, int cur){
    t[cur].l = l; t[cur].r = r;
    t[cur].maxv = t[cur].lsum = t[cur].rsum = -inf;
    t[cur].sum = 0;
    if(l == r){
        t[cur].maxv = t[cur].lsum = t[cur].rsum = t[cur].sum = 1LL * arr[l];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, cur<<1);
    build(mid + 1, r, cur<<1|1);
    pushup(cur);
}
void change(int pos, int x, int cur){
    if(t[cur].l == t[cur].r){
        if(t[cur].l == pos) t[cur].maxv = t[cur].lsum = t[cur].rsum = t[cur].sum = x;
        return;
    }
    int mid = t[cur].l + t[cur].r >> 1;
    if(pos <= mid) change(pos, x, cur<<1);
    else change(pos, x, cur<<1|1);
    pushup(cur);
}
Tree query(int l , int r, int cur){
    Tree a, b, c;
    if(l <= t[cur].l && t[cur].r <= r){
        return t[cur];
    }
    int mid = t[cur].l + t[cur].r >> 1;
    a.sum = a.lsum = a.rsum = a.maxv = -inf - 1;
    b.sum = b.lsum = b.rsum = b.maxv = -inf - 1;
    c.lsum = c.rsum = c.maxv = -inf - 1; c.sum = 0;
    if(l <= mid){
        a = query(l, r, cur << 1);
        c.sum += a.sum;
    }
    if(mid < r){
        b = query(l, r, cur<<1|1);
        c.sum += b.sum;
    }
    c.lsum = max(a.lsum, a.sum + b.lsum);
    c.rsum = max(b.rsum, a.rsum + b.sum);
    c.maxv = max(a.maxv, max(b.maxv, a.rsum + b.lsum));
    return c;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &arr[i]);
    }
    build(1, n, 1);
    while(m--){
        int k, l, r;
        scanf("%d %d %d", &k, &l, &r);
        if(k == 1){
            printf("%lld\n", query(min(l, r), max(l, r), 1).maxv);
        }
        else{
            change(l, r, 1);
        }
    }
    getchar(); getchar();
}

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 4e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);
int gcd(int a,int b)    { return b == 0 ? a : gcd(b, a % b); }

int n, m, e, ans, f[maxn];
struct Node{
    int l, r, val;
    bool operator <(Node a){
        return r < a.r;
    }
}arr[maxn];
struct Tree{
    int l, r, minv;
}tree[maxn];

inline void pushup(int cur){
    tree[cur].minv = min(tree[cur<<1].minv, tree[cur<<1|1].minv);
}
void build(int l, int r, int cur){
    tree[cur].l = l; tree[cur].r = r;
    if(l == r){
        tree[cur].minv = l == m - 1 ? 0 : inf;
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, cur<<1);
    build(mid + 1, r, cur<<1|1);
    pushup(cur);
}
void modify(int pos, int x, int cur)
{
    if(tree[cur].l == tree[cur].r){
        tree[cur].minv = x;
        return;
    }
    int mid = tree[cur].l + tree[cur].r >> 1;
    if(pos <= mid)    modify(pos, x, cur << 1);
    else modify(pos, x, cur<<1|1);
    pushup(cur);
}
void query(int l, int r, int cur)
{
    if(l <= tree[cur].l && tree[cur].r <= r){
        ans = min(ans, tree[cur].minv);
        return;
    }
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if(l <= mid) query(l,r,cur<<1);
    if(mid < r)  query(l,r,cur<<1|1);
}

int main()
{
    scanf("%d %d %d", &n, &m, &e); m += 1; e += 1;
    for(int i = 1; i <= n; ++i){
        scanf("%d %d %d", &arr[i].l, &arr[i].r, &arr[i].val);
        arr[i].l++; arr[i].r++;
    }
    sort(arr + 1, arr + n + 1);
    memset(f, inf, sizeof(f));
    build(m - 1, e, 1);
    int res = inf;
    for(int i = 1; i <= n; ++i){
        ans = inf;
        query(arr[i].l - 1, min(arr[i].r - 1, e), 1);
        f[arr[i].r] = min(f[arr[i].r], ans + arr[i].val);
        modify(arr[i].r, f[arr[i].r], 1);
        if(arr[i].r >= e)   res = min(res, f[arr[i].r]);
    }
    printf("%d\n", res == inf ? -1 : res);
    getchar(); getchar();
}

#include <bits/stdc++.h>

using namespace std;
const int maxn = 4e6 + 10;
const int inf = 0x3f3f3f3f;

struct node{
    int l, r, minv;
}tree[maxn];
struct Node{
    int l, r;
    bool operator <(Node a){
        return r < a.r;
    }
}arr[maxn];
int n, t, f[maxn];
int ans;

inline void pushup(int cur){
    tree[cur].minv = min(tree[cur<<1].minv, tree[cur<<1|1].minv);
}
void build(int l, int r, int cur){
    tree[cur].l = l; tree[cur].r = r;
    if(l == r){
        tree[cur].minv = l == 0 ? 0 : inf;
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, cur<<1);
    build(mid + 1, r, cur<<1|1);
    pushup(cur);
}
void modify(int pos, int x, int cur)
{
    if(tree[cur].l == tree[cur].r){
        if(tree[cur].l == pos)  tree[cur].minv = x;
        return;
    }
    int mid = tree[cur].l + tree[cur].r >> 1;
    if(pos <= mid)  modify(pos, x, cur<<1);
    else modify(pos, x, cur<<1|1);
    pushup(cur);
}
void query(int l, int r, int cur){
    if(l <= tree[cur].l && tree[cur].r <= r){
        ans = min(ans, tree[cur].minv);
        return;
    }
    int mid = tree[cur].l + tree[cur].r >> 1;
    if(l <= mid)    query(l, r, cur<<1);
    if(mid < r) query(l, r, cur<<1|1);
}

int main()
{
    scanf("%d %d", &n, &t);
    build(0, t, 1);
    for(int i = 1; i <= n; ++i){
        scanf("%d %d", &arr[i].l, &arr[i].r);
    }
    sort(arr + 1, arr + n + 1);
    memset(f, inf, sizeof(f));
    int res = inf;
    for(int i = 1; i <= n; ++i){
        ans = inf;
        query(arr[i].l - 1, arr[i].r - 1, 1);
        f[arr[i].r] = min(f[arr[i].r], ans + 1);
        modify(arr[i].r, f[arr[i].r], 1);
        if(arr[i].r >= t)   res = min(res, f[arr[i].r]);
    }
    printf("%d\n", res == inf ? -1 : res);
    getchar(); getchar();
}