#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a > G,rG,T,C; vector vs,used,blg; SCC(){} SCC(Int n):n(n),G(n),rG(n),used(n),blg(n){} void add_edge(Int from,Int to){ G[from].emplace_back(to); rG[to].emplace_back(from); } void dfs(Int v){ used[v]=1; for(Int u:G[v]) if(!used[u]) dfs(u); vs.emplace_back(v); } void rdfs(Int v,Int k){ used[v]=1; blg[v]=k; C[k].emplace_back(v); for(Int u:rG[v]) if(!used[u]) rdfs(u,k); } Int build(){ for(Int v=0;v=0;i--){ if(!used[vs[i]]){ T.emplace_back(); C.emplace_back(); rdfs(vs[i],k++); } } for(Int v=0;v>n>>m; vector l(n),r(n); for(Int i=0;i>l[i]>>r[i],r[i]++; auto check=[&](Int al,Int ar,Int bl,Int br){ return max(al,bl)