Problem: Let's call a graph with n vertices, each of which has it's own point A_i = (x_i, y_i) with integer coordinates, a planar tree if:

  * All points A_1, A_2, …, A_n are different and no three points lie on the same line. 
  * The graph is a tree, i.e. there are exactly n-1 edges there exists a path between any pair of vertices. 
  * For all pairs of edges (s_1, f_1) and (s_2, f_2), such that s_1 ≠ s_2, s_1 ≠ f_2, f_1 ≠ s_2, and f_1 ≠ f_2, the segments A_{s_1} A_{f_1} and A_{s_2} A_{f_2} don't intersect. 



Imagine a planar tree with n vertices. Consider the convex hull of points A_1, A_2, …, A_n. Let's call this tree a spiderweb tree if for all 1 ≤ i ≤ n the following statements are true:

  * All leaves (vertices with degree ≤ 1) of the tree lie on the border of the convex hull. 
  * All vertices on the border of the convex hull are leaves. 



An example of a spiderweb tree: 

<image>

The points A_3, A_6, A_7, A_4 lie on the convex hull and the leaf vertices of the tree are 3, 6, 7, 4.

Refer to the notes for more examples.

Let's call the subset S ⊂ \{1, 2, …, n\} of vertices a subtree of the tree if for all pairs of vertices in S, there exists a path that contains only vertices from S. Note that any subtree of the planar tree is a planar tree.

You are given a planar tree with n vertexes. Let's call a partition of the set \{1, 2, …, n\} into non-empty subsets A_1, A_2, …, A_k (i.e. A_i ∩ A_j = ∅ for all 1 ≤ i < j ≤ k and A_1 ∪ A_2 ∪ … ∪ A_k = \{1, 2, …, n\}) good if for all 1 ≤ i ≤ k, the subtree A_i is a spiderweb tree. Two partitions are different if there exists some set that lies in one parition, but not the other.

Find the number of good partitions. Since this number can be very large, find it modulo 998 244 353.

Input

The first line contains an integer n (1 ≤ n ≤ 100) — the number of vertices in the tree.

The next n lines each contain two integers x_i, y_i (-10^9 ≤ x_i, y_i ≤ 10^9) — the coordinates of i-th vertex, A_i.

The next n-1 lines contain two integers s, f (1 ≤ s, f ≤ n) — the edges (s, f) of the tree.

It is guaranteed that all given points are different and that no three of them lie at the same line. Additionally, it is guaranteed that the given edges and coordinates of the points describe a planar tree.

Output

Print one integer — the number of good partitions of vertices of the given planar tree, modulo 998 244 353.

Examples

Input


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


Output


5


Input


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


Output


8


Input


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


Output


13


Input


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


Output


36

Note

<image> The picture for the first sample.

In the first test case, all good partitions are:

  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\}. 



The partition \{1, 2, 3\}, \{4\} isn't good, because the subtree \{1, 2, 3\} isn't spiderweb tree, since the non-leaf vertex 1 lies on the convex hull.

The partition \{2, 3, 4\}, \{1\} isn't good, because the subset \{2, 3, 4\} isn't a subtree.

<image> The picture for the second sample.

In the second test case, the given tree isn't a spiderweb tree, because the leaf vertex 1 doesn't lie on the convex hull. However, the subtree \{2, 3, 4, 5\} is a spiderweb tree.

<image> The picture for the third sample. <image> The picture for the fourth sample.

In the fourth test case, the partition \{1, 2, 3, 4\}, \{5, 6, 7, 8\} is good because all subsets are spiderweb subtrees.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int RangeFind(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcountll(nValue);
}
inline int bitnum(long long nValue) { return __builtin_popcountll(nValue); }
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  if (a == 0) return 0;
  return 64 - __builtin_clzll(a);
}
inline int bitmaxl(long long a) {
  if (a == 0) return 0;
  return 64 - __builtin_clzll(a);
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1& a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
bool output_deb = 0;
struct Point {
  union {
    double co[2];
    struct {
      double x, y;
    };
  };
  double ang;
  Point(double a = 0, double b = 0) : x(a), y(b) { ang = 0; }
  Point operator+(const Point& a) const {
    Point ans;
    ans.x = x + a.x;
    ans.y = y + a.y;
    return ans;
  }
  Point operator-(const Point& a) const {
    Point ans;
    ans.x = x - a.x;
    ans.y = y - a.y;
    return ans;
  }
  double operator*(const Point& a) const { return x * a.x + y * a.y; }
  double operator%(const Point& a) const { return x * a.y - y * a.x; }
  Point operator*(const double p) const {
    Point ans;
    ans.x = x * p;
    ans.y = y * p;
    return ans;
  }
};
double GetAngle(const double x, const double y) {
  if (x == 0) {
    if (y > 0)
      return pi / 2;
    else
      return pi / 2 * 3;
  }
  if (x > 0) {
    if (y < 0)
      return atan(y / x) + pi * 2;
    else
      return atan(y / x);
  } else {
    return atan(y / x) + pi;
  }
}
double GetAngle(const Point& p) { return GetAngle(p.x, p.y); }
bool In(const Point& cen, const Point& a, const Point& b) {
  return jud((a - cen) % (b - cen), 0) >= 0;
}
bool Inter(const Point& a, const Point& b, const Point& c, const Point& d) {
  if (min(a.x, b.x) > max(c.x, d.x) || min(a.y, b.y) > max(c.y, d.y) ||
      min(c.x, d.x) > max(a.x, b.x) || min(c.y, d.y) > max(a.y, b.y))
    return 0;
  double h, i, j, k;
  h = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  i = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x);
  j = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x);
  k = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);
  return h * i <= eps && j * k <= eps;
}
struct Line {
  Point a, b;
  double ang;
  Line(const Point& a1 = Point(0, 0), const Point& b1 = Point(1, 0))
      : a(a1), b(b1) {
    Point temp = b1 - a1;
    ang = GetAngle(temp.x, temp.y);
  }
  friend bool Contain(Line l, Point a);
  bool operator==(const Line& rline) const {
    return Contain(*this, rline.a) && Contain(*this, rline.b);
  }
};
inline bool Contain(const Line& l, const Point& a) {
  return jud((a - l.a) % (l.b - l.a), 0) == 0;
}
Point GetInter(const Line& la, const Line& lb) {
  double sa = (lb.a - la.a) % (lb.a - la.b);
  double sb = (lb.b - la.b) % (lb.b - la.a);
  Point ans = (lb.a * sb + lb.b * sa) * (1.0 / (sb + sa));
  return ans;
}
const int MAXN = 110;
int n;
Point orig[MAXN];
int fa[MAXN], depth[MAXN];
vector<int> e[MAXN];
const int mod = 998244353;
long long dp[MAXN], rdp[MAXN][MAXN][4];
int in_order[MAXN], lin, to[MAXN];
pair<int, int> range[MAXN];
vector<int> route[MAXN][MAXN];
void ReMap() {
  Point rorig[MAXN];
  for (int i = 0; i < n; i++) {
    rorig[to[i]] = orig[i];
  }
  memcpy(orig, rorig, sizeof(rorig));
  vector<int> re[MAXN];
  for (int i = 0; i < n; i++) {
    for (const auto it : e[i]) {
      re[to[i]].push_back(to[it]);
    }
  }
  for (int i = 0; i < n; i++) e[i] = re[i];
  int rfa[MAXN], rdepth[MAXN];
  for (int i = 0; i < n; i++) {
    rfa[to[i]] = fa[i] == -1 ? -1 : to[fa[i]];
    rdepth[to[i]] = to[depth[i]];
  }
  for (int i = 0; i < n; i++) {
    fa[i] = rfa[i];
    depth[i] = rdepth[i];
  }
}
void GetRoute(int no) {
  int q[MAXN], lq = 0, from[MAXN];
  q[lq++] = no;
  from[no] = -1;
  for (int i = 0; i < n; i++) route[no][i].clear();
  for (int i = 0; i < lq; i++) {
    int rno = q[i];
    for (const auto nxt : e[rno])
      if (nxt != from[rno]) {
        q[lq++] = nxt;
        from[nxt] = rno;
        route[no][nxt] = route[no][rno];
        route[no][nxt].push_back(nxt);
      }
  }
}
bool CanConnect(int a, int b, int intersection) {
  for (const auto rno : route[a][intersection]) {
    if (!In(orig[a], orig[b], orig[rno])) {
      return false;
    }
  }
  for (const auto rno : route[b][intersection]) {
    if (!In(orig[a], orig[b], orig[rno])) {
      return false;
    }
  }
  return true;
}
void DfsInit(int no) {
  for (const auto rno : e[no])
    if (rno != fa[no]) {
      fa[rno] = no;
      depth[rno] = depth[no] + 1;
      DfsInit(rno);
    }
}
void DfsOrder(int no) {
  in_order[lin] = no;
  to[no] = lin;
  range[lin].first = lin;
  lin++;
  for (const auto rno : e[no])
    if (rno != fa[no]) {
      DfsOrder(rno);
    }
  range[to[no]].second = lin;
}
pair<int, int> all_seg[MAXN * MAXN * 2];
int lall_seg;
void DfsDp(int no) {
  if (dp[no] != -1) return;
  dp[no] = 0;
  for (int i = range[no].first + 1; i != range[no].second; i++) {
    DfsDp(i);
  }
  memset(rdp, 0, sizeof(rdp));
  long long multi[MAXN][MAXN];
  memset(multi, 0, sizeof(multi));
  lall_seg = 0;
  for (int i = range[no].first; i <= range[no].second; i++) {
    for (int j = range[no].first; j <= range[no].second; j++) {
      if (CanConnect(i, j, no) && i != range[no].second &&
          j != range[no].second && i != j) {
        int ri = i, rj = j;
        if (ri > rj) swap(ri, rj);
        if (range[ri].second <= rj || ri == no)
          all_seg[lall_seg++] = make_pair(i, j);
      }
      if (j >= i) {
        multi[i][j] = 1;
        if (range[i].second > j && j != i && i != no) {
          multi[i][j] = 0;
          continue;
        }
        for (int k = i + 1; k < j;) {
          if (range[k].second > j) {
            k++;
          } else {
            multi[i][j] *= dp[k];
            multi[i][j] %= mod;
            k = range[k].second;
          }
        }
      }
    }
  }
  for (int i = range[no].first + 1; i < range[no].second; i++) {
    for (int j = range[no].first; j < i; j++) {
      multi[i][j] =
          multi[i][range[no].second] * multi[range[no].first][j] % mod;
    }
  }
  dp[no] = 1;
  for (const auto it : e[no])
    if (it != fa[no]) {
      dp[no] *= dp[it];
      dp[no] %= mod;
    }
  sort(all_seg, all_seg + lall_seg,
       [&](const pair<int, int>& a, const pair<int, int>& b) {
         double ang1 = GetAngle(orig[a.second] - orig[a.first]);
         double ang2 = GetAngle(orig[b.second] - orig[b.first]);
         if (jud(ang1, ang2) == 0) return a < b;
         return ang1 < ang2;
       });
  memset(rdp, 0, sizeof(rdp));
  for (int i = 0; i < lall_seg; i++) {
    int flag_or = 0;
    int st = all_seg[i].first, en = all_seg[i].second;
    if (st != no && en != no && route[no][st][0] != route[no][en][0]) {
      flag_or |= 2;
    }
    if (en == no) flag_or |= 1;
    for (int from = no; from < range[no].second; from++)
      if (from != st)
        for (int flag = 0; flag < 4; flag++)
          if (rdp[from][st][flag]) {
            int nxt_flag = flag | flag_or;
            rdp[from][en][nxt_flag] += rdp[from][st][flag] * multi[st][en];
            rdp[from][en][nxt_flag] %= mod;
          }
    rdp[st][en][flag_or] += multi[st][en];
    rdp[st][en][flag_or] %= mod;
  }
  for (int i = no; i < range[no].second; i++) {
    dp[no] += rdp[i][i][1];
    dp[no] += rdp[i][i][2];
  }
  dp[no] %= mod;
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%lf%lf", &orig[i].x, &orig[i].y);
  }
  if (orig[0].x == 678721121) {
    output_deb = 0;
  }
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    e[a].push_back(b);
    e[b].push_back(a);
  }
  fa[0] = -1;
  DfsInit(0);
  for (int i = 0; i < n; i++) {
    pair<double, int> sort_arr[MAXN];
    memset(sort_arr, 0, sizeof(sort_arr));
    double angfa = fa[i] == -1 ? pi * 2 : GetAngle(orig[fa[i]] - orig[i]);
    for (int j = 0; j < (int)e[i].size(); j++) {
      sort_arr[j] = make_pair(GetAngle(orig[e[i][j]] - orig[i]), e[i][j]);
      if (jud(sort_arr[j].first, angfa) == 1) sort_arr[j].first -= pi * 2;
    }
    sort(sort_arr, sort_arr + e[i].size());
    for (int j = 0; j < (int)e[i].size(); j++) {
      e[i][j] = sort_arr[j].second;
    }
    if (output_deb) {
      for (int j = 0; j < (int)e[i].size(); j++) {
        cout << sort_arr[j].first << '|' << sort_arr[j].second;
      }
      cout << endl;
    }
  }
  if (output_deb) {
    cout << 1 << endl;
  }
  DfsOrder(0);
  if (output_deb) {
    cout << 2 << endl;
  }
  range[n] = make_pair(n, n + 1);
  ReMap();
  if (output_deb) {
    cout << 13 << endl;
  }
  for (int i = 0; i < n; i++) GetRoute(i);
  if (output_deb) {
    cout << 4 << endl;
  }
  assert(lin == n);
  for (int i = 0; i < n; i++) {
    assert(range[i].first == i);
  }
  for (int i = 1; i < n; i++) {
    assert(e[i].back() == fa[i]);
  }
  memset(dp, -1, sizeof(dp));
  if (output_deb) {
    cout << 5 << endl;
  }
  DfsDp(0);
  cout << dp[0] << endl;
  return 0;
}