题目描述

在一个无限大的二维平面上，有 $n$ 个点 $p_i=(x_i,y_i)$ 和 $n-1$ 条边 $e_i=(u_i,v_i)$，保证任意两点连通，即构成一棵无根树。我们称满足没有两个点重合、三个点共线、两条边相交的树为“平面树”。保证这棵树为平面树。

当这棵树的所有叶子（度数 $\le 1$ 的顶点）都在凸包的边界上，且凸包边界上的所有顶点都是叶子，我们称它为“凸包树”。一个凸包树的例子如下（点 $p_3,p_6,p_7,p_4$ 位于凸包上，树的叶子顶点为 $3,6,7,4$）：

【图片】

我们称顶点集合 $S \subseteq \{1, 2, \dots, n\}$ 为树的子树，当且仅当对于 $S$ 中的任意一对顶点，存在一条仅包含 $S$ 中顶点的路径。易得平面树的任意子树也是平面树。

给定一棵有 $n$ 个顶点的平面树。我们将集合 $\{1, 2, \ldots, n\}$ 的一个划分称为好的划分，若它被划分为若干不相交非空子集 $A_1, A_2, \ldots, A_k$，且所有 $A_i$ 的并为 $\{1, 2, \ldots, n\}$，并且对于所有 $1 \leq i \leq k$，子树 $A_i$ 都是“凸包树”。若存在某个集合只出现在一个划分中，则两个划分不同。

请计算好的划分的数量。由于答案可能很大，请输出对 $998244353$ 取模的结果。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $x_i, y_i$，表示顶点 $p_i$ 的坐标。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$，表示树中的一条边 $e_i$。

输出格式

输出一个整数，表示给定平面树的顶点的好的划分数量，对 $998244353$ 取模。

样例 1 输入

4
0 0
0 1
-1 -1
1 -1
1 2
1 3
1 4

样例 1 输出

5

样例 2 输入

5
3 2
0 -3
-5 -3
5 -5
4 5
4 2
4 1
5 2
2 3

样例 2 输出

8

样例 3 输入

6
4 -5
0 1
-2 8
3 -10
0 -1
-4 -5
2 5
3 2
1 2
4 6
4 2

样例 3 输出

13

样例 4 输入

8
0 0
-1 2
-2 5
-5 1
1 3
0 3
2 4
-1 -4
1 2
3 2
5 6
4 2
1 5
5 7
5 8

样例 4 输出

36

数据范围

本题使用子任务（Subtask）计分。你需要通过一个子任务内所有测试数据才可以获得相应的得分。

对于所有测试数据，保证：

• $1\le n\le100$；
• $-10^9\le x_i,y_i \le 10^9$；
• $1\le u_i,v_i\le n$。

特殊性质 A：保证 $u_i=i,v_i=i+1$。

特殊性质 B：保证 $u_i=1,v_i=i+1$。

特殊性质 C：保证 $-10\le x_i,y_i \le10$。