Consider the cumulative sum array \(b=(b_0,b_1,\ldots,b_N)\). In other words, for each \(i\ (0 \leq i \leq N)\), \(b_i\) is the sum of first \(i\) terms of \(a\).

Then, the information that Takahashi will give can be rephrased as follows:

• The \(i\)-th piece of information: the value \(a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}=b_{r_i}-b_{l_i-1}\)

At first, all information we have about \(b\) is that \(b_0\) has the value \(0\). Therefore, the sum of all elements in \(a\), or \(a_1+a_2+\cdots+a_N=b_N\), can be determined if and only if:

• we can reach \(b_N\) from \(b_0\) by traversing some pieces of information.

Strictly speaking, the condition can be described as follows.

• Prepare a graph with \(N+1\) vertices and \(0\) edges, whose vertices are number from \(0\) through \(N\). Then, add a undirected edge from each \(i\ (1 \leq i \leq Q)\) between Vertex \(l_i-1\) and Vertex \(r_i\). The condition is that Vertex \(0\) and Vertex \(N\) are connected.

This can be checked with Breadth-First Search or Union-Find Tree in a total of \(O(N+Qα(N))\) time, where the function \(α\) denotes the inverse of Ackerman function.

Sample code (C++)

#include<bits/stdc++.h>
using namespace std;

//union_find_tree
struct union_find{
    int N;
    vector<int> par, siz;
    union_find(int n) : N(n){
        par.resize(N);
        siz.resize(N, 1);
        for(int i=0; i<N; i++) par[i] = i;
    }
    int root(int X){
        if(par[X] == X) return X;
        return par[X] = root(par[X]);
    }
    bool same(int X, int Y){
        return root(X) == root(Y);
    }
    void unite(int X, int Y){
        X = root(X);
        Y = root(Y);
        if(X == Y) return;
        if(siz[Y] < siz[X]) std::swap(X, Y);
        par[X] = Y;
        siz[Y] += siz[X];
        siz[X] = 0;
    }
};

int main(){
	int N,Q; cin >> N >> Q;
	union_find tree(N+1);
	while(Q--){
		int l,r; cin >> l >> r;
		tree.unite(l-1,r);
	}
	string ans = "No";
	if(tree.same(0,N)) ans = "Yes";
	cout << ans << endl;
}