#include #include #include using namespace __gnu_pbds; using namespace std; template using os = tree, rb_tree_tag, tree_order_statistics_node_update>; template using oms = tree, rb_tree_tag, tree_order_statistics_node_update>; #define mod 1000000007 #define mod2 998244353 #define ll long long #define bl __int128_t #define pb push_back #define all(v) v.begin(),v.end() #define bs binary_search #define rall(v) v.rbegin(),v.rend() #define lb lower_bound #define ub upper_bound #define pl pair #define f(i,n) for(ll i=0;i a(n); f(i,n) cin>>a[i] #define pyes cout<<"YES\n" #define pno cout<<"NO\n" #pragma GCC optimize("unroll-loops") #pragma gcc optimize("Ofast") #pragma GCC optimization("Ofast") #pragma optimize(Ofast) #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("popcnt") /*void mat_mul(ll a[101][101],ll b[101][101],ll mv,ll z){ ll mul[mv][mv]; for (ll i=0;i0){ if(n%2) mat_mul(a,m,mv,z); n/=2; mat_mul(m,m,mv,z); for(ll i=0;i0){ if(y%2) res=(res*x)%z; y/=2; if(y) x=(x*x)%z; }return res%z; } /*ll gcd(ll a,ll b,ll& x,ll& y){ x=1,y=0; ll x1=0,y1=1,a1=a,b1=b; while(b1){ ll q=a1/b1; tie(x,x1)=make_tuple(x1,x-q*x1); tie(y,y1)=make_tuple(y1,y-q*y1); tie(a1,b1)=make_tuple(b1,a1-q*b1); }return a1; }*/ vector isP(1e3+5,1); void setP(){ isP[0]=isP[1]=0; for(ll i=2;i*i<1e3+5;i++){ if(isP[i]==1) for(ll j=i*i;j<1e3+5;j+=i) isP[j]=0; }return; } vector pr; void getP(){ //pr.push_back(2); for(ll i=3;i<1e5;i+=2) if(isP[i]) pr.push_back(i); } #define MX 1e6 vector spf(MX+2,1); void sieve(){ spf[0]=0; for(ll i=2;i<3;i++){ if(spf[i]==1){ for(ll j=i;jn) return 0; if(n-rn) return 0; return (((fac[n]*facNumInv[r])%z)*facNumInv[n-r])%z; }*/ /* vector getPF(ll x){ vector res; map mp; while(x!=1){ if(mp[spf[x]]==0) res.push_back(spf[x]); mp[spf[x]]++,x/=spf[x]; }return res; }*/ /*bool isBipc(vector>& v2,ll src,vector& color){ color[src] = 1; queue q; q.push(src); while (!q.empty()) { ll u = q.front(); q.pop(); for(auto z : v2[u]){ if(color[z]==-1) color[z]=1-color[u],q.push(z); else if(color[z]==color[u]) return false; } }return true; } bool isBip(vector>& v2,vector& color){ ll n=v2.size(),i; for(i=1;i<=n;i++) if(color[i]==-1 && !(isBipc(v2,i,color))) return false; return true; }*/ /*ll num1,num2; template // T -> node, U->update. struct Lsegtree{ vectorst; vectorlazy; ll n; T identity_element; // related to query U identity_update; // related to update Lsegtree(ll n, T identity_element, U identity_update) { this->n = n; this->identity_element = identity_element; this->identity_update = identity_update; st.assign(4*n,identity_element); lazy.assign(4*n, identity_update); } T combine(T l, T r) { // change this function as required. // related to query T ans = max(l,r); return ans; } void buildUtil(ll v, ll tl, ll tr, vector&a) { if(tl == tr) { st[v]=a[tl]; return; } ll tm = (tl + tr)/2; buildUtil(2*v + 1, tl, tm,a); buildUtil(2*v + 2,tm+1,tr,a); st[v] = combine(st[2*v + 1], st[2*v + 2]); } // change the following 2 functions, and you're more or less done. T apply(T curr, U upd, ll tl, ll tr) { // related to update and query T ans = upd; return ans; } U combineUpdate(U old_upd, U new_upd, ll tl, ll tr) { // related to update U ans = old_upd; ans=new_upd; return ans; } void push_down(ll v, ll tl, ll tr) { if(lazy[v] == identity_update)return; st[v] = apply(st[v], lazy[v], tl, tr); if(2*v + 2 < 4*n) { ll tm = (tl + tr)>>1; lazy[2*v + 1] = combineUpdate(lazy[2*v+1], lazy[v], tl, tm); lazy[2*v + 2] = combineUpdate(lazy[2*v+2], lazy[v], tm+1,tr); } lazy[v] = identity_update; } T queryUtil(ll v, ll tl, ll tr, ll l, ll r) { push_down(v,tl,tr); if(l > r)return identity_element; if(tr < l or tl > r) { return identity_element; } if(l <= tl and r >= tr) { return st[v]; } ll tm = (tl + tr)>>1; return combine(queryUtil(2*v+1,tl,tm,l,r), queryUtil(2*v+2,tm+1,tr,l,r)); } void updateUtil(ll v, ll tl, ll tr, ll l, ll r, U upd) { push_down(v,tl,tr); if(tr < l or tl > r)return; if(tl >=l and tr <=r) { lazy[v] = combineUpdate(lazy[v],upd,tl,tr); push_down(v,tl,tr); } else { ll tm = (tl + tr)/2; updateUtil(2*v+1,tl,tm,l,r,upd); updateUtil(2*v+2,tm+1,tr,l,r,upd); st[v] = combine(st[2*v + 1], st[2*v+2]); } } void build(vectora) { assert(a.size() == n); buildUtil(0,0,n-1,a); } T query(ll l, ll r) { return queryUtil(0,0,n-1,l,r); } void update(ll l,ll r, U upd) { updateUtil(0,0,n-1,l,r,upd); } ll find_ind(ll v,ll tl,ll tr,ll x){ // have to store maximums for this to work if(st[v]=x) return find_ind(v+v+1,tl,tm,x); else return find_ind(v+v+2,tm+1,tr,x-st[v+v+1]); } };*/ int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q; //sieve(); // for SPF //setP(); //getP(); //cin>>t; map mp,mp2,mp3; //compfac(z2); string s,s2; while(t--){ cin>>n; multiset v; f(i,n){ cin>>x>>y; v.insert({x,y}); } ll ans=-1; vector vis(n,false); while(v.size()>0){ pl cur; auto it=v.begin(); while(it!=v.end()){ cur=*it; v.erase(v.find(*it)); it=v.lb({cur.second,0ll}); }ans++; } cout<