#include #define debug(x) cerr << #x << ": " << x << '\n' #define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector vll; const ll INF = INT_MAX; const ll MOD = 20171211; struct Edge{ ll dst; Edge(ll t):dst(t){} }; using Edges=vector; using Graph=vector; vector> SCC(const Graph& g,vector &I) { ll n=g.size(); vector> scc; vector S, B; I.assign(n,0); function dfs = [&](int u) { B.push_back(I[u] = S.size()); S.push_back(u); for(Edge e: g[u]) { int v=e.dst; if (!I[v]) dfs(v); else while (I[v] < B.back()) B.pop_back(); } if (I[u] == B.back()) { scc.push_back({}); B.pop_back(); for (; I[u] < (int)S.size(); S.pop_back()) { scc.back().push_back(S.back()); I[S.back()] = n + scc.size(); } } }; for(int u=0;u>N>>M; vll L(N),R(N); for(ll i=0;i>L[i]>>R[i]; } Graph G(2*N); for(ll i=0;i idx; vector> scc=SCC(G,idx); /* debug(scc.size()); debugArray(idx,N*2); */ bool isok=true; for(ll i=0;i