{"raw_statement":[{"iden":"statement","content":"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.\n\nTo 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$.\n\nIt's difficult to satisfy everyone's aesthetic, so the tree should meet some constraints. \n\nThere are $m$ constraints of type $1$ and $k$ constraints of type $2$.\n\nThe $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$.\n\nThe $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$. \n\nFor 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$. \n\nYou 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$.\n\nThere 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.\n\nThe first line contains three integers $n, m, k (2 <= n <= 60, 0 <= m <= n -1, 0 <= k <= 60)$.\n\nThe $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)$. \n\nThe $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)$. \n\nOutput one integer in a single line.\n\nIn sample $1$, there are $3$ trees that meet all constraints.\n\nIn sample $2$, there is only $1$ tree that meets all constraints.\n\nIn sample $3$, there is no tree that simultaneously meets all constraints.\n\n"},{"iden":"input","content":"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)$. "},{"iden":"output","content":"Output one integer in a single line."},{"iden":"examples","content":"Input4 3 1\n1 2\n2 1\n1 2\n1 1 1\nOutput3Input4 3 1\n1 2\n2 3\n1 4\n0 1 2\nOutput1Input4 3 0\n1 2\n2 3\n3 1\nOutput0"},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of juniors.  \nLet $ 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 $.\n\n**Constraints**  \n$ 1 \\leq n \\leq 2 \\cdot 10^5 $\n\n**Objective**  \nFind the maximum value of  \n$$\nH = \\sum_{j=1}^{k} j \\cdot s_{l+j-1}\n$$  \nover 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 $.  \n(Note: $ H = 0 $ if no treats are given, i.e., $ k = 0 $.)\n\nEquivalently, for every possible subarray $ S[l:r] = (s_l, s_{l+1}, \\dots, s_r) $, define:  \n$$\nH(l, r) = \\sum_{i=0}^{r-l} (i+1) \\cdot s_{l+i}\n$$  \nMaximize $ H(l, r) $ over all $ 1 \\leq l \\leq r \\leq n $, and include $ H = 0 $ as an option.","simple_statement":"You are given n juniors, each with a treat value s_i.  \nYou can choose any contiguous subarray (by removing any prefix and/or suffix).  \nFor the chosen subarray of length k, the happiness score is:  \n1 * (first value) + 2 * (second value) + ... + k * (last value).  \nFind the maximum possible happiness score.","has_page_source":false}