Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

brute force

combinatorics

dp

dsu

math

two pointers

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Mercenaries

time limit per test

7 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputPolycarp 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

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

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

Examples

Input

3 0 1 1 2 3 1 3

Output

3

Input

3 1 1 1 2 3 1 3 2 3

Output

2

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 10:50:12 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|