SP16277 TAP2013C - Little Red-Cap

从前有一个活泼的女孩，总是戴着一顶红色的小帽子，因此大家都叫她小红帽。小红帽很喜欢在森林里散步，一边散步一边用她的小篮子收集浆果，把它们送给会做出全地区最美味糕点的奶奶。不过，小红帽特别不喜欢森林里的危险，尤其是那只非常饥饿且喜欢窥伺的大灰狼。 一天，小红帽决定从家出发去奶奶家。她计划在途中采些浆果，并尽可能安全地完成这次旅行。小红帽的家在森林最西边的空地，而她奶奶的家则位于最东边的空地。在她们之间，还有若干其他的空地，上面长满了浆果树。这片森林非常密集，所以通过空地之间的道路是唯一的通行方式，幸好小红帽对这些道路非常熟悉。为了不迷路，小红帽总是选择通往更东方向的道路。为了避免被大灰狼伏击，她必须清楚地知道，从当前位置到奶奶家的所有可能路径的数量。 在森林中，一条路径是由从西向东排列的一系列空地组成，每片空地通过道路与下一片相连。而_通往奶奶家的路径_则是以她奶奶家的空地为终点的路径。每片空地的_选择水平_是指从该空地到奶奶家的所有路径数量。类似地，一条路径的_选择水平_是构成该路径的所有空地的选择水平之和。为了避开大灰狼，小红帽想找到一条从家到奶奶家具有最大选择水平的路径。你能帮助她吗？

第一行包含两个整数 $N$ 和 $S$，分别表示森林中的空地数量和路径数量（$3 \leq N \leq 3 \times 10^4$，$2 \leq S \leq 10^5$）。空地由 $1$ 到 $N$ 的不同整数标识，并按从西到东的顺序排列，如果 $1 \leq i < j \leq N$，则空地 $i$ 在空地 $j$ 的西边。小红帽家在空地 $1$，她奶奶的家在空地 $N$。 接下来的 $S$ 行，每行由两个整数 $I$ 和 $J$ 构成，表示在空地 $I$ 和空地 $J$ 之间有一条道路（$1 \leq I < J \leq N$）。确保至少有一条从小红帽家到奶奶家的路径，并且所有路径中的最大选择水平不超过 $10^{18}$。

输出一个整数，表示从小红帽家到奶奶家的最大选择水平。 **本翻译由 AI 自动生成**