← 返回题目列表

Codeforces · 1400/G

G. 雇佣兵

中文机器翻译题面 查看原题

Polycarp 玩一个(又一个!)战略电脑游戏。在这款游戏中,他领导着一支雇佣兵军队。

坡旅甲想要集结他的军队来执行任务。有$$$n$$$雇佣兵可供雇佣,军队应该由其中的某些子集组成。

如果所选雇佣兵的最终数量不小于$$$l_i$$$(否则他认为任务注定失败)并且不大于$$$r_i$$$(他不想与太多其他雇佣兵分享奖杯),则可以选择第$$$i$$$个雇佣兵。此外,$$$m$$$ 的雇佣兵彼此憎恨,不能被选中执行同一任务。

Polycarp 需要考虑多少个非空子集?换句话说,计算非空雇佣兵子集的数量,使得该子集的大小对于每个选定的雇佣兵属于$$$[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$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$)。

接下来是 $$$m$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i < b_i \le n$$$) 表示雇佣兵 $$$a_i$$$ 和 $$$b_i$$$ 互相仇恨。此列表中没有两个相等的对。

输出

打印一个整数 — 满足约束的非空子集的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

3 0
1 1
2 3
1 3

输出 #1

3

输入 #2

3 1
1 1
2 3
1 3
2 3

输出 #2

2