Mercenaries

题意翻译

有$n$个人和$m$对敌对关系，每一个人有一个条件区间$[l_i,r_i]$。 现在要在这$n$个人中选**若干个人**。定义一个合法的选择$\{S\}$，当且仅当对于$\{S\}$中的所有人$i$，$l_i\le |S| \le r_i$，且$\{S\}$中所有人互不敌对。 求有多少种合法的选择，答案对$998244353$取模。 $1\le n\le 3\times 10^5$，$0\le m\le \min\{20,\frac{n(n-1)}{2}\}$，$1\le l_i\le r_i\le n$。

题目描述

Polycarp plays a (yet another!) strategic computer game. In this game, he leads an army of mercenaries. Polycarp wants to gather his army for a quest. There are $ n $ mercenaries for hire, and the army should consist of some subset of them. The $ i $ -th mercenary can be chosen if the resulting number of chosen mercenaries is not less than $ l_i $ (otherwise he deems the quest to be doomed) and not greater than $ r_i $ (he doesn't want to share the trophies with too many other mercenaries). Furthermore, $ m $ pairs of mercenaries hate each other and cannot be chosen for the same quest. How many non-empty subsets does Polycarp need to consider? In other words, calculate the number of non-empty subsets of mercenaries such that the size of this subset belongs to $ [l_i, r_i] $ for each chosen mercenary, and there are no two mercenaries in the subset that hate each other. The answer may be large, so calculate it modulo $ 998244353 $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 3 \cdot 10^5 $ , $ 0 \le m \le \min(20, \dfrac{n(n-1)}{2}) $ ) — the number of mercenaries and the number of pairs of mercenaries that hate each other. Then $ n $ lines follow, the $ i $ -th of them contains two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ). Then $ m $ lines follow, the $ i $ -th of them contains two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i < b_i \le n $ ) denoting that the mercenaries $ a_i $ and $ b_i $ hate each other. There are no two equal pairs in this list.

输出格式

Print one integer — the number of non-empty subsets meeting the constraints, taken modulo $ 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