让我们调用一个具有 $$$n$$$ 顶点的图,每个顶点都有自己的点 $$$A_i = (x_i, y_i)$$$ 具有整数坐标,平面树如果:
- 所有点 $$$A_1、A_2、\ldots、A_n$$$ 都不同,并且没有三个点位于同一条线上。
- 该图是一棵树,即恰好有 $$$n-1$$$ 边,任何一对顶点之间都存在路径。
- 对于所有边对 $$$(s_1, f_1)$$$ 和 $$$(s_2, f_2)$$$,使得 $$$s_1 \neq s_2, s_1 \neq f_2,$$$ $$$f_1 \neq s_2$$$ 和 $$$f_1 \neq f_2$$$,段$$$A_{s_1} A_{f_1}$$$ 和 $$$A_{s_2} A_{f_2}$$$ 不相交。
想象一棵具有 $$$n$$$ 个顶点的平面树。考虑点 $$$A_1, A_2, \ldots, A_n$$$ 的凸包。如果对于所有 $$$1 \leq i \leq n$$$ 下列陈述成立,我们称这棵树为蜘蛛网树:
- 树的所有叶子(度数 $$$\leq 1$$$ 的顶点)位于凸包的边界上。
- 凸包边界上的所有顶点都是叶子。
蜘蛛网树的示例:
点 $$$A_3, A_6, A_7, A_4$$$ 位于凸包上,树的叶顶点是 $$$3, 6, 7, 4$$$。
请参阅注释以获取更多示例。
如果对于 $$$S$$$ 中的所有顶点对,存在一条仅包含来自 $$$S$$$ 的顶点的路径,我们将顶点的子集 $$$S \subset \{1, 2, \ldots, n\}$$$ 称为树的子树。请注意,平面树的任何子树都是平面树。
给你一棵有 $$$n$$$ 个顶点的平面树。我们将集合 $$$\{1, 2, \ldots, n\}$$$ 划分为非空子集 $$$A_1, A_2, \ldots, A_k$$$ (即 $$$A_i \cap A_j = \emptyset$$$ 对于所有 $$$1 \leq i < j \leq k$$$ 和 $$$A_1 \cup A_2 \cup \ldots \cup A_k = \{1, 2, \ldots, n\}$$$) 如果对于所有 $$$1 \leq i \leq k$$$,子树 $$$A_i$$$ 是一棵蜘蛛网树,那就很好。如果一个分区中存在某个集合,而另一个分区中不存在,则两个分区是不同的。
查找良好分区的数量。由于这个数字可能非常大,因此请对 $$$998\,244\,353$$$ 求模。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 树中的顶点数。
接下来的 $$$n$$$ 行每行包含两个整数 $$$x_i, y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — 第 $$$i$$$ 个顶点的坐标 $$$A_i$$$。
接下来的 $$$n-1$$$ 行包含两个整数 $$$s, f$$$ ($$$1 \leq s, f \leq n$$$) - 树的边 $$$(s, f)$$$。
保证所有给定的点都不同,并且没有三个点位于同一条线上。此外,保证给定的边和点的坐标描述平面树。
输出
打印一个整数 - 给定平面树的顶点的良好分区数,以 $$$998\,244\,353$$$ 为模。
示例
输入 #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
注意
第一个样本的图片。
在第一个测试用例中,所有好的分区是:
1. $$$\{1\}$$$, $$$\{2\}$$$, $$$\{3\}$$$, $$$\{4\}$$$;
2. $$$\{1, 2\}$$$, $$$\{3\}$$$, $$$\{4\}$$$;
3. $$$\{1, 3\}$$$, $$$\{2\}$$$, $$$\{4\}$$$;
4. $$$\{1, 4\}$$$, $$$\{2\}$$$, $$$\{3\}$$$;
5. $$$\{1, 2, 3, 4\}$$$.
分区 $$$\{1, 2, 3\}$$$, $$$\{4\}$$$ 不好,因为子树 $$$\{1, 2, 3\}$$$ 不是蜘蛛网树,因为非叶顶点 $$$1$$$ 位于凸包上。
分区 $$$\{2, 3, 4\}$$$, $$$\{1\}$$$ 不好,因为子集 $$$\{2, 3, 4\}$$$ 不是子树。
第二个示例的图片。
在第二个测试用例中,给定的树不是蜘蛛网树,因为叶顶点 $$$1$$$ 并不位于凸包上。然而,子树 $$$\{2, 3, 4, 5\}$$$ 是一棵蜘蛛网树。
第三个样本的图片。
第四个样本的图片。
在第四个测试用例中,分区 $$$\{1, 2, 3, 4\}$$$, $$$\{5, 6, 7, 8\}$$$ 很好,因为所有子集都是蜘蛛网子树。