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 int MOD = 998244353;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = acos((long double)-1);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
int pct(int x) { return __builtin_popcount(x); }
int bit(int x) { return 31 - __builtin_clz(x); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
template <class A>
void re(complex<A>& c);
template <class A, class B>
void re(pair<A, B>& p);
template <class A>
void re(vector<A>& v);
template <class A, size_t SZ>
void re(array<A, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& d) {
  string t;
  re(t);
  d = stod(t);
}
void re(long double& d) {
  string t;
  re(t);
  d = stold(t);
}
template <class H, class... T>
void re(H& h, T&... t) {
  re(h);
  re(t...);
}
template <class A>
void re(complex<A>& c) {
  A a, b;
  re(a, b);
  c = {a, b};
}
template <class A, class B>
void re(pair<A, B>& p) {
  re(p.first, p.second);
}
template <class A>
void re(vector<A>& x) {
  for (auto& a : x) re(a);
}
template <class A, size_t SZ>
void re(array<A, SZ>& x) {
  for (auto& a : x) re(a);
}
template <class A, class B>
string to_string(pair<A, B> p);
template <class A>
string to_string(complex<A> c) {
  return to_string(make_pair(c.real(), c.imag()));
}
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(char c) {
  string second = "";
  second += c;
  return second;
}
string to_string(string second) { return second; }
string to_string(const char* second) { return (string)second; }
string to_string(vector<bool> v) {
  bool fst = 1;
  string res = "{";
  for (int i = (0); i < ((int)v.size()); ++i) {
    if (!fst) res += ", ";
    fst = 0;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t SZ>
string to_string(bitset<SZ> b) {
  string res = "";
  for (int i = (0); i < (SZ); ++i) res += char('0' + b[i]);
  return res;
}
template <class T>
string to_string(T v) {
  bool fst = 1;
  string res = "{";
  for (const auto& x : v) {
    if (!fst) res += ", ";
    fst = 0;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class A>
void pr(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void pr(const H& h, const T&... t) {
  pr(h);
  pr(t...);
}
void ps() { pr("\n"); }
template <class H, class... T>
void ps(const H& h, const T&... t) {
  pr(h);
  if (sizeof...(t)) pr(" ");
  ps(t...);
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void unsyncIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
void setIO(string second = "") {
  unsyncIO();
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
struct mi {
  typedef decay<decltype(MOD)>::type T;
  T v;
  explicit operator T() const { return v; }
  mi() { v = 0; }
  mi(long long _v) {
    v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
    if (v < 0) v += MOD;
  }
  friend bool operator==(const mi& a, const mi& b) { return a.v == b.v; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.v < b.v; }
  friend void re(mi& a) {
    long long x;
    re(x);
    a = mi(x);
  }
  friend string to_string(mi a) { return to_string(a.v); }
  mi& operator+=(const mi& m) {
    if ((v += m.v) >= MOD) v -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((v -= m.v) < 0) v += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    v = (long long)v * m.v % MOD;
    return *this;
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
  }
  mi operator-() const { return mi(-v); }
  mi& operator++() { return *this += 1; }
  mi& operator--() { return *this -= 1; }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
vector<vector<mi>> comb;
void genComb(int SZ) {
  comb.assign(SZ, vector<mi>(SZ));
  comb[0][0] = 1;
  for (int i = (1); i < (SZ); ++i)
    for (int j = (0); j < (i + 1); ++j)
      comb[i][j] = comb[i - 1][j] + (j ? comb[i - 1][j - 1] : 0);
}
int sgn(long long a) { return (a > 0) - (a < 0); }
long long sq(long long a) { return a * a; }
namespace Point {
long long norm(const pair<long long, long long>& p) {
  return sq(p.first) + sq(p.second);
}
long long abs(const pair<long long, long long>& p) { return sqrt(norm(p)); }
long long arg(const pair<long long, long long>& p) {
  return atan2(p.second, p.first);
}
pair<long long, long long> conj(const pair<long long, long long>& p) {
  return pair<long long, long long>(p.first, -p.second);
}
pair<long long, long long> perp(const pair<long long, long long>& p) {
  return pair<long long, long long>(-p.second, p.first);
}
pair<long long, long long> dir(long long ang) {
  return pair<long long, long long>(cos(ang), sin(ang));
}
pair<long long, long long> operator-(const pair<long long, long long>& l) {
  return pair<long long, long long>(-l.first, -l.second);
}
pair<long long, long long> operator+(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return pair<long long, long long>(l.first + r.first, l.second + r.second);
}
pair<long long, long long> operator-(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return pair<long long, long long>(l.first - r.first, l.second - r.second);
}
pair<long long, long long> operator*(const pair<long long, long long>& l,
                                     const long long& r) {
  return pair<long long, long long>(l.first * r, l.second * r);
}
pair<long long, long long> operator*(const long long& l,
                                     const pair<long long, long long>& r) {
  return r * l;
}
pair<long long, long long> operator/(const pair<long long, long long>& l,
                                     const long long& r) {
  return pair<long long, long long>(l.first / r, l.second / r);
}
pair<long long, long long> operator*(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return pair<long long, long long>(l.first * r.first - l.second * r.second,
                                    l.second * r.first + l.first * r.second);
}
pair<long long, long long> operator/(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return l * conj(r) / norm(r);
}
pair<long long, long long>& operator+=(pair<long long, long long>& l,
                                       const pair<long long, long long>& r) {
  return l = l + r;
}
pair<long long, long long>& operator-=(pair<long long, long long>& l,
                                       const pair<long long, long long>& r) {
  return l = l - r;
}
pair<long long, long long>& operator*=(pair<long long, long long>& l,
                                       const long long& r) {
  return l = l * r;
}
pair<long long, long long>& operator/=(pair<long long, long long>& l,
                                       const long long& r) {
  return l = l / r;
}
pair<long long, long long>& operator*=(pair<long long, long long>& l,
                                       const pair<long long, long long>& r) {
  return l = l * r;
}
pair<long long, long long>& operator/=(pair<long long, long long>& l,
                                       const pair<long long, long long>& r) {
  return l = l / r;
}
pair<long long, long long> unit(const pair<long long, long long>& p) {
  return p / abs(p);
}
long long dot(const pair<long long, long long>& a,
              const pair<long long, long long>& b) {
  return a.first * b.first + a.second * b.second;
}
long long cross(const pair<long long, long long>& a,
                const pair<long long, long long>& b) {
  return a.first * b.second - a.second * b.first;
}
long long cross(const pair<long long, long long>& p,
                const pair<long long, long long>& a,
                const pair<long long, long long>& b) {
  return cross(a - p, b - p);
}
pair<long long, long long> reflect(const pair<long long, long long>& p,
                                   const pair<long long, long long>& a,
                                   const pair<long long, long long>& b) {
  return a + conj((p - a) / (b - a)) * (b - a);
}
pair<long long, long long> foot(const pair<long long, long long>& p,
                                const pair<long long, long long>& a,
                                const pair<long long, long long>& b) {
  return (p + reflect(p, a, b)) / (long long)2;
}
bool onSeg(const pair<long long, long long>& p,
           const pair<long long, long long>& a,
           const pair<long long, long long>& b) {
  return cross(a, b, p) == 0 && dot(p - a, p - b) <= 0;
}
ostream& operator<<(ostream& os, const pair<long long, long long>& p) {
  return os << "(" << p.first << "," << p.second << ")";
}
};  // namespace Point
using namespace Point;
int n, par[101], depth[101];
pair<long long, long long> pos[201];
mi dp[101], childProd[101];
vector<int> adj[101];
bool ccw(int a, int b, int c) { return cross(pos[a], pos[b], pos[c]) >= 0; }
vector<int> tot;
void genChild(int x) {
  tot.push_back(x);
  for (auto& t : adj[x]) genChild(t);
}
vector<int> path(int a, int b) {
  int _a = a, _b = b;
  vector<int> x, y;
  while (a != b) {
    if (depth[a] > depth[b]) {
      x.push_back(a);
      a = par[a];
    } else {
      y.push_back(b);
      b = par[b];
    }
  }
  reverse(begin(y), end(y));
  x.push_back(a);
  x.insert(end(x), begin(y), end(y));
  return x;
}
bool bet(pair<long long, long long> a, pair<long long, long long> b,
         pair<long long, long long> c) {
  if (cross(a, c) > 0) {
    return cross(a, b) > 0 && cross(b, c) > 0;
  }
  return cross(a, b) > 0 || cross(b, c) > 0;
}
mi get(int a, int b, int c) {
  mi prod = 1;
  for (auto& t : adj[b]) {
    if (t == a || t == c) continue;
    if (bet(pos[a] - pos[b], pos[t] - pos[b], pos[c] - pos[b])) {
      prod *= dp[t];
    }
  }
  return prod;
}
mi val(int x, int y) {
  if (x == y) return 0;
  vector<int> v = path(x, y);
  for (auto& t : v)
    if (!ccw(x, y, t)) return 0;
  mi prod = 1;
  for (auto& t : adj[x])
    if (t != v[1]) prod *= dp[t];
  for (int i = (1); i < ((int)v.size() - 1); ++i)
    prod *= get(v[i - 1], v[i], v[i + 1]);
  return prod;
}
mi nex[201][201];
mi lo[201][201], hi[201][201];
vector<int> TMP[201];
mi solveConvex(vector<int> c) {
  mi res = 0;
  sort(begin(c), end(c), [&](int x, int y) { return pos[x] < pos[y]; });
  for (int i = (0); i < ((int)c.size()); ++i) {
    vector<pair<pair<long long, long long>, int>> tmp;
    for (int j = (0); j < ((int)c.size()); ++j)
      if (nex[c[i]][c[j]] != 0 || nex[c[j]][c[i]] != 0) {
        if (j < i)
          tmp.push_back({pos[c[i]] - pos[c[j]], j});
        else
          tmp.push_back({pos[c[j]] - pos[c[i]], j});
      }
    sort(begin(tmp), end(tmp),
         [](pair<pair<long long, long long>, int> x,
            pair<pair<long long, long long>, int> y) {
           return cross(x.first, y.first) > 0;
         });
    TMP[i].clear();
    for (auto& t : tmp) TMP[i].push_back(t.second);
  }
  for (int st = (0); st < ((int)c.size()); ++st) {
    for (int a = (0); a < ((int)c.size()); ++a)
      for (int b = (a + 1); b < ((int)c.size()); ++b) lo[a][b] = hi[a][b] = 0;
    for (int i = (st); i < ((int)c.size()); ++i) {
      mi LO = (i == st);
      for (auto& t : TMP[i]) {
        if (t < i)
          LO += lo[t][i];
        else
          lo[i][t] = nex[c[i]][c[t]] * LO;
      }
      reverse(begin(TMP[i]), end(TMP[i]));
      mi HI = (i == st);
      for (auto& t : TMP[i]) {
        if (t < i)
          HI += hi[t][i];
        else
          hi[i][t] = nex[c[t]][c[i]] * HI;
      }
      reverse(begin(TMP[i]), end(TMP[i]));
      if (i != st) res += LO * HI;
    }
  }
  return res;
}
int makeEd(int a, int b) {
  assert(abs(depth[a] - depth[b]) == 1);
  if (depth[a] < depth[b]) return b;
  return a + n;
}
mi deal(vector<int> c, int a) {
  auto _c = c;
  vector<int> verts;
  for (auto& x : c) verts.push_back(x), verts.push_back(x + n);
  for (auto& x : verts)
    for (auto& y : verts) nex[x][y] = 0;
  for (auto& x : c)
    for (auto& y : c) {
      mi z = val(x, y);
      if (!ccw(x, y, a)) z = 0;
      if (z == 0) continue;
      vector<int> v = path(x, y);
      nex[makeEd(v[1], x)][makeEd(v[(int)v.size() - 2], y)] = z;
    }
  return solveConvex(verts);
}
void dfs(int a) {
  childProd[a] = 1;
  for (auto& t : adj[a]) dfs(t), childProd[a] *= dp[t];
  dp[a] = childProd[a];
  tot.clear();
  genChild(a);
  dp[a] += deal(tot, a);
  for (auto& t : adj[a]) {
    tot.clear();
    genChild(t);
    dp[a] -= deal(tot, a);
  }
}
void genDepth(int x) {
  for (auto& t : adj[x]) {
    par[t] = x;
    depth[t] = depth[x] + 1;
    pos[t + n] = pos[x];
    adj[t].erase(find(begin(adj[t]), end(adj[t]), x));
    genDepth(t);
  }
}
int main() {
  setIO();
  re(n);
  for (int i = (1); i < (n + 1); ++i) re(pos[i]);
  for (int i = (0); i < (n - 1); ++i) {
    int a, b;
    re(a, b);
    adj[a].push_back(b), adj[b].push_back(a);
  }
  genDepth(1);
  dfs(1);
  ps(dp[1]);
}