CF1400G Mercenaries

Polycarp 正在玩一款（又一款！）策略类电脑游戏。在这款游戏中，他领导着一支雇佣兵军队。 Polycarp 想要召集他的军队去执行一个任务。有 $n$ 个雇佣兵可供雇佣，军队应由他们的某个子集组成。 第 $i$ 个雇佣兵可以被选中，当且仅当被选中的雇佣兵总人数不少于 $l_i$（否则他认为任务注定失败），且不多于 $r_i$（他不想和太多其他雇佣兵分享战利品）。此外，有 $m$ 对雇佣兵彼此憎恨，不能被同时选中参加同一个任务。 Polycarp 需要考虑多少个非空的雇佣兵子集？换句话说，计算满足以下条件的雇佣兵非空子集的数量：对于每个被选中的雇佣兵 $i$，子集的大小属于 $[l_i, r_i]$，且子集中没有两名彼此憎恨的雇佣兵。 答案可能很大，请输出对 $998244353$ 取模后的结果。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 3 \cdot 10^5$，$0 \le m \le \min(20, \dfrac{n(n-1)}{2})$）——雇佣兵的数量和互相憎恨的雇佣兵对数。 接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）。 接下来 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i < b_i \le n$），表示雇佣兵 $a_i$ 和 $b_i$ 互相憎恨。列表中没有重复的对。

输出一个整数，表示满足条件的非空子集数量，对 $998244353$ 取模。

由 ChatGPT 4.1 翻译