The beautiful campus of University of Shanghai for Science and Technology is lined with trees. It takes ten years to grow trees and a hundred years to nurture talents. The trees have witnessed the growth of generations. Unconsciously, the season of graduation has quietly arrived.
To commemorate the contributions of seniors to the algorithm contest of University of Shanghai for Science and Technology, everyone decides to plant an unrooted tree of $n$ vertices in the school. Vertices are numbered from $1$ to $n$.
It's difficult to satisfy everyone's aesthetic, so the tree should meet some constraints.
There are $m$ constraints of type $1$ and $k$ constraints of type $2$.
The $i$-th constraint of type $1$ can be represented by a pair $(x_i, y_i)$, which indicates there should be an edge connecting vertex $x_i$ and vertex $y_i$.
The $i$-th constraint of type $2$ can be represented by a triple $(o p_i, x_i, d e g_i)$. $o p_i$ indicates the type of the restriction, $1$ for the upper limit and $0$ for the lower limit. $x_i$ indicates the number of the vertex. $d e g_i$ indicates the extreme value of degree of vertex $x_i$.
For example, the constraint triple $(1, 3, 1)$ means that the degree of vertex $3$ should be *at most* $1$, and the constraint triple $(0, 1, 2)$ means that the degree of vertex $1$ should be *at least* $2$.
You need to count how many kinds of trees meet all constraints simultaneously. Notice that the answer might be very large, so please output the desired answer modulo $998244353$.
There are some definitions you may need to know: an undirected connected graph is a tree if and only if it has $n$ vertices and $n -1$ edges; two trees are considered different if and only if their adjacency matrixes are different.
The first line contains three integers $n, m, k (2 <= n <= 60, 0 <= m <= n -1, 0 <= k <= 60)$.
The $i$-th of the next $m$ lines contains two integers $x_i, y_i (1 <= x_i, y_i <= n, x_i eq.not y_i)$.
The $i$-th of the next $k$ lines contains three integers $o p_i, x_i, d e g_i (0 <= o p_i <= 1, 1 <= x_i <= n, 0 <= d e g_i < n)$.
Output one integer in a single line.
In sample $1$, there are $3$ trees that meet all constraints.
In sample $2$, there is only $1$ tree that meets all constraints.
In sample $3$, there is no tree that simultaneously meets all constraints.
## Input
The first line contains three integers $n, m, k (2 <= n <= 60, 0 <= m <= n -1, 0 <= k <= 60)$.The $i$-th of the next $m$ lines contains two integers $x_i, y_i (1 <= x_i, y_i <= n, x_i eq.not y_i)$. The $i$-th of the next $k$ lines contains three integers $o p_i, x_i, d e g_i (0 <= o p_i <= 1, 1 <= x_i <= n, 0 <= d e g_i < n)$.
## Output
Output one integer in a single line.
[samples]
## Note
In sample $1$, there are $3$ trees that meet all constraints. In sample $2$, there is only $1$ tree that meets all constraints. In sample $3$, there is no tree that simultaneously meets all constraints.
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of juniors.
Let $ S = (s_1, s_2, \dots, s_n) $ be a sequence of integers, where $ s_i \in \mathbb{Z} $ and $ |s_i| \leq 10^7 $.
**Constraints**
$ 1 \leq n \leq 2 \cdot 10^5 $
**Objective**
Find the maximum value of
$$
H = \sum_{j=1}^{k} j \cdot s_{l+j-1}
$$
over all contiguous subsequences $ (s_l, s_{l+1}, \dots, s_{l+k-1}) $ of $ S $, where $ 1 \leq l \leq l+k-1 \leq n $, and $ k \geq 0 $.
(Note: $ H = 0 $ if no treats are given, i.e., $ k = 0 $.)
Equivalently, for every possible subarray $ S[l:r] = (s_l, s_{l+1}, \dots, s_r) $, define:
$$
H(l, r) = \sum_{i=0}^{r-l} (i+1) \cdot s_{l+i}
$$
Maximize $ H(l, r) $ over all $ 1 \leq l \leq r \leq n $, and include $ H = 0 $ as an option.