Mercenaries
Contest: Educational Codeforces Round 94 (Rated for Div. 2)
Difficulty rating: 2600
Tags: bitmasks, brute force, combinatorics, dp, dsu, math, two pointers

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$$$.

Input format:
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.

Output format:
Print one integer — the number of non-empty subsets meeting the constraints, taken modulo $$$998244353$$$.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Example input:
3 0
1 1
2 3
1 3

Example output:
3

Example input:
3 1
1 1
2 3
1 3
2 3

Example output:
2

Editorial:
We will use inclusion-exclusion formula to solve this problem (you may read about it here: https://cp-algorithms.com/combinatorics/inclusion-exclusion.html). To put it simply, we are going to count the number of subsets that meet the restrictions on $$$[l_i, r_i]$$$, ignoring the edges (I'll call the pairs of mercenaries that hate each other "edges" for simplicity). This number is not the answer, since we counted some subsets that violate the conditions for the edges — so, for each edge, we count the number of subsets that violate the condition on that edge, and subtract it from the answer. But it means that if a subset violates the conditions on multiple edges, we subtracted it multiple times, so, for each pair of edges, we count the subsets that violate both edges in that pair and add them back, then remove the subsets violating the triples, and so on. The mathematical formula for the answer is $$$\sum \limits_{E \in S} f(E)$$$, where $$$S$$$ is the set containing all $$$2^m$$$ subsets of edges, and $$$f(E)$$$ is the number of subsets that meet the constraints on $$$[l_i, r_i]$$$, and violate the constraints for every edge $$$e \in E$$$.
Now we have to calculate $$$f(E)$$$ efficiently, since the outer loop already runs in $$$O(2^m)$$$. If we have to violate a set of edges, then we have a set of mercenaries that we should take (the "endpoints" of the edges), and the number of those mercenaries (let's denote it as $$$k$$$) is up to $$$40$$$. The size of the subset should meet the constraints on $$$[l_i, r_i]$$$ for each of those mercenaries, so let's intersect the segments $$$[l_i, r_i]$$$ for them (and if the intersection is empty, then there are no subsets that violate all of those edges). Let the intersection of those segments be $$$[L, R]$$$. The naive solution would be to iterate on the size of the subset and calculate the number of ways to compose a subset that contains some fixed mercenaries of given size (if the size is $$$s$$$, and $$$c_s$$$ is the number of mercenaries that are willing to be in a subset of size $$$s$$$, then we have to add $$${{c_s - k} \choose {s - k}}$$$ to the answer). So, for each subset $$$E$$$, $$$f(E) = \sum \limits_{s = L}^{R} {{c_s - k} \choose {s - k}}$$$. This sum can be calculated in $$$O(1)$$$ as follows: note that $$$k$$$ is up to $$$40$$$, so for every possible value of $$$k$$$, precalculate the array of prefix sums of those binomial coefficients. This precalculation runs in $$$O(nm + n \log MOD)$$$, and each $$$f(E)$$$ can be calculated in $$$O(m \log m)$$$, so overall the complexity is $$$O(nm + n \log MOD + 2^m m \log m)$$$.