Problem: Today DZY begins to play an old game. In this game, he is in a big maze with n rooms connected by m corridors (each corridor allows to move in both directions). You can assume that all the rooms are connected with corridors directly or indirectly.

DZY has got lost in the maze. Currently he is in the first room and has k lives. He will act like the follows:

  * Firstly he will randomly pick one of the corridors going from his current room. Each outgoing corridor has the same probability to be picked. 
  * Then he will go through the corridor and then the process repeats. 



There are some rooms which have traps in them. The first room definitely has no trap, the n-th room definitely has a trap. Each time DZY enters one of these rooms, he will lost one life. Now, DZY knows that if he enters the n-th room with exactly 2 lives, firstly he will lost one live, but then he will open a bonus round. He wants to know the probability for him to open the bonus round. Please, help him.

Input

The first line contains three integers n, m, k (2 ≤ n ≤ 500; 1 ≤ m ≤ 105; 2 ≤ k ≤ 109).

The second line contains n integers, each of them is either 0 or 1. If the i-th number is 1, then the i-th room has a trap, otherwise it has not a trap. Please note, that the number of rooms with a trap is no more than 101. It is guaranteed that the first room has no trap, and the n-th room has a trap.

Then m lines follows. Each of them contains two integers ui, vi (1 ≤ ui, vi ≤ n; ui ≠ vi), meaning that current corridor connects two rooms ui and vi. It is guaranteed that the corridor system is connected.

Output

Print the only real number — the probability for DZY to open the bonus round. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

Examples

Input

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


Output

0.25000000


Input

3 2 2
0 1 1
1 2
2 3


Output

-0.00000000


Input

2 1 3
0 1
1 2


Output

1.00000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
std::istream &operator>>(std::istream &i, pair<T, U> &p) {
  i >> p.first >> p.second;
  return i;
}
template <typename T>
std::istream &operator>>(std::istream &i, vector<T> &t) {
  for (auto &v : t) {
    i >> v;
  }
  return i;
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &o, const pair<T, U> &p) {
  o << p.first << ' ' << p.second;
  return o;
}
template <typename T>
std::ostream &operator<<(std::ostream &o, const vector<T> &t) {
  if (t.empty()) o << '\n';
  for (size_t i = 0; i < t.size(); ++i) {
    o << t[i] << " \n"[i == t.size() - 1];
  }
  return o;
}
template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using maxheap = priority_queue<T, vector<T>, less<T>>;
template <typename T>
bool in(T a, T b, T c) {
  return a <= b && b < c;
}
unsigned int logceil(int first) {
  return 8 * sizeof(int) - __builtin_clz(first);
}
namespace std {
template <typename T, typename U>
struct hash<pair<T, U>> {
  hash<T> t;
  hash<U> u;
  size_t operator()(const pair<T, U> &p) const {
    return t(p.first) ^ (u(p.second) << 7);
  }
};
}  // namespace std
template <typename T, typename F>
T bsh(T l, T h, const F &f) {
  T r = -1, m;
  while (l <= h) {
    m = (l + h) / 2;
    if (f(m)) {
      l = m + 1;
      r = m;
    } else {
      h = m - 1;
    }
  }
  return r;
}
template <typename F>
double bshd(double l, double h, const F &f, double p = 1e-9) {
  unsigned int r = 3 + (unsigned int)log2((h - l) / p);
  while (r--) {
    double m = (l + h) / 2;
    if (f(m)) {
      l = m;
    } else {
      h = m;
    }
  }
  return (l + h) / 2;
}
template <typename T, typename F>
T bsl(T l, T h, const F &f) {
  T r = -1, m;
  while (l <= h) {
    m = (l + h) / 2;
    if (f(m)) {
      h = m - 1;
      r = m;
    } else {
      l = m + 1;
    }
  }
  return r;
}
template <typename F>
double bsld(double l, double h, const F &f, double p = 1e-9) {
  unsigned int r = 3 + (unsigned int)log2((h - l) / p);
  while (r--) {
    double m = (l + h) / 2;
    if (f(m)) {
      h = m;
    } else {
      l = m;
    }
  }
  return (l + h) / 2;
}
template <typename T>
T gcd(T a, T b) {
  if (a < b) swap(a, b);
  return b ? gcd(b, a % b) : a;
}
template <typename T>
class vector2 : public vector<vector<T>> {
 public:
  vector2() {}
  vector2(size_t a, size_t b, T t = T())
      : vector<vector<T>>(a, vector<T>(b, t)) {}
};
template <typename T>
class vector3 : public vector<vector2<T>> {
 public:
  vector3() {}
  vector3(size_t a, size_t b, size_t c, T t = T())
      : vector<vector2<T>>(a, vector2<T>(b, c, t)) {}
};
template <typename T>
class vector4 : public vector<vector3<T>> {
 public:
  vector4() {}
  vector4(size_t a, size_t b, size_t c, size_t d, T t = T())
      : vector<vector3<T>>(a, vector3<T>(b, c, d, t)) {}
};
template <typename T>
class vector5 : public vector<vector4<T>> {
 public:
  vector5() {}
  vector5(size_t a, size_t b, size_t c, size_t d, size_t e, T t = T())
      : vector<vector4<T>>(a, vector4<T>(b, c, d, e, t)) {}
};
template <typename T>
class Matrix {
 public:
  Matrix(size_t R, size_t C, T t = T(0))
      : R(R), C(C), A(R, vector<T>(C, t)), def(t) {}
  Matrix(const vector<vector<T>> &a, T t = T(0))
      : R(a.size()), C(a[0].size()), A(a), def(t) {}
  Matrix(const initializer_list<vector<T>> &a, T t = T(0))
      : R(a.size()), C(a.begin()->size()), A(a), def(t) {}
  size_t rows() const { return R; }
  size_t columns() const { return C; }
  bool isSquare() const { return R * C; }
  bool isIdentity() const {
    for (int i = 0; i < min(R, C); ++i) {
      for (int j = 0; j < min(R, C); ++j) {
        if (i == j && A[i][j] != 1) return false;
        if (i != j && A[i][j] != 0) return false;
      }
    }
    return true;
  }
  void addColumnsRight(size_t add, T t = T()) {
    for (int i = 0; i < R; ++i) {
      A[i].resize(C + add);
      for (size_t j = C; j < C + add; ++j) A[i][j] = t;
    }
    C += add;
  }
  void removeColumnsLeft(size_t rem) {
    for (size_t i = 0; i < R; ++i)
      A[i].erase(A[i].begin(),
                 rem > A[i].size() ? A[i].end() : A[i].begin() + rem);
  }
  T determinant() const {
    if (!isSquare()) {
      throw std::runtime_error(
          "Cannot compute determinant of a rectangular matrix");
    }
    Matrix<T> tmp(*this);
    T ans = tmp.toReducedRowEchelon();
    if (tmp.isIdentity())
      return ans;
    else
      return 0;
  }
  vector<T> solveFor(const vector<T> &b) {
    if (!isSquare()) {
      throw std::runtime_error("Cannot solve a rectangular matrix");
    }
    if (b.size() != R)
      throw new std::runtime_error(
          "Unable to solve linear equation, dimensions do not match");
    Matrix<T> tmp(*this);
    for (int i = 0; i < R; ++i) tmp.A[i].push_back(b[i]);
    ++tmp.C;
    tmp.toReducedRowEchelon();
    if (!tmp.isIdentity())
      throw std::runtime_error("Cannot solve a singular matrix");
    vector<T> Ans(R);
    for (int j = 0; j < R; ++j) Ans[j] = tmp.A[j].back();
    return Ans;
  }
  Matrix<T> power(unsigned long long N) {
    if (!isSquare()) {
      throw std::runtime_error(
          "Cannot compute determinant of a rectangular matrix");
    }
    Matrix<T> ans(R, R, 0), pow = *this;
    for (unsigned int r = 0; r < R; ++r) ans[r][r] = 1;
    while (N) {
      if (N & 1) ans = ans * pow;
      N >>= 1;
      pow = pow * pow;
    }
    return ans;
  }
  Matrix<T> &operator+=(const Matrix<T> &m) {
    if (R != m.R)
      throw std::runtime_error("Cannot add matrices of different height");
    if (C != m.C)
      throw std::runtime_error("Cannot add matrices of different width");
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        A[i][j] += m.A[i][j];
      }
    }
    return *this;
  }
  Matrix<T> &operator-=(const Matrix<T> &m) {
    if (R != m.R)
      throw std::runtime_error("Cannot substract matrices of different height");
    if (C != m.C)
      throw std::runtime_error("Cannot substract matrices of different width");
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        A[i][j] -= m.A[i][j];
      }
    }
    return *this;
  }
  Matrix<T> operator*(const Matrix<T> &m) const {
    if (C != m.R)
      throw std::runtime_error("Matrices incompatible for multiplication");
    Matrix<T> Ans(R, m.C, T(0));
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < m.C; ++j) {
        for (int k = 0; k < C; ++k) {
          Ans[i][j] += A[i][k] * m.A[k][j];
        }
      }
    }
    return Ans;
  }
  vector<T> operator*(const vector<T> &m) const {
    if (C != m.size())
      throw std::runtime_error(
          "Matric and vector incompatible for multiplication");
    vector<T> ans(R, def);
    for (unsigned int r = 0; r < R; ++r) {
      for (unsigned int c = 0; c < C; ++c) {
        ans[r] += m[c] * (*this)[r][c];
      }
    }
    return ans;
  }
  class Row {
   public:
    Row(Matrix<T> *M, size_t row) : M(M), row(row) {}
    T &operator[](size_t col) {
      if (col < 0 || col >= M->C) throw std::out_of_range("Invalid column ID");
      return M->A[row][col];
    }
    const T &operator[](size_t col) const {
      if (col < 0 || col >= M->C) throw std::out_of_range("Invalid column ID");
      return M->A[row][col];
    }

   private:
    Matrix<T> *M;
    size_t row;
  };
  Row operator[](size_t row) {
    if (row < 0 || row >= R) throw std::out_of_range("Invalid row ID");
    return Row(this, row);
  }
  const Row operator[](size_t row) const {
    if (row < 0 || row >= R) throw std::out_of_range("Invalid row ID");
    return Row(const_cast<Matrix<T> *>(this), row);
  }
  Matrix<T> transposed() const {
    Matrix<T> M(*this);
    M.transpose();
    return M;
  }
  Matrix<T> inverted() const {
    if (R != C) throw std::runtime_error("Matrix not square");
    Matrix<T> M(*this);
    M.invert();
    return M;
  }
  Matrix<T> &transpose() {
    A.resize(max(R, C));
    for (size_t i = 0; i < C; ++i) A[i].resize(max(R, C));
    for (size_t i = 0; i < R; ++i) {
      for (size_t j = i + 1; j < C; ++j) swap(A[i][j], A[j][i]);
    }
    for (size_t i = 0; i < C; ++i) A[i].resize(R);
    A.resize(C);
    return *this;
  }
  Matrix<T> &invert() {
    addColumnsRight(C, def);
    for (size_t i = 0; i < R; ++i) A[i][R + i] = 1;
    toReducedRowEchelon();
    if (!isIdentity()) throw std::runtime_error("Matrix not invertible");
    removeColumnsLeft(C / 2);
    return *this;
  }

 private:
  T toReducedRowEchelon() {
    size_t pivot = 0;
    T factor = 1;
    for (size_t i = 0; i < C && pivot < R; ++i) {
      pair<T, size_t> Q = {A[pivot][i], pivot};
      for (size_t j = pivot + 1; j < R; ++j)
        if (A[j][i] != 0) Q = {A[j][i], j};
      if (Q.first == 0) continue;
      if (Q.second != i) swap(A[Q.second], A[pivot]);
      for (size_t j = i + 1; j < C; ++j) A[pivot][j] /= A[pivot][i];
      factor /= A[pivot][i];
      A[pivot][i] = 1;
      for (size_t j = 0; j < R; ++j) {
        if (j != pivot) {
          for (size_t k = i + 1; k < C; ++k) A[j][k] -= A[pivot][k] * A[j][i];
          A[j][i] = 0;
        }
      }
      ++pivot;
    }
    return factor;
  }
  size_t R, C;
  vector<vector<T>> A;
  T def;
};
template <typename T>
std::ostream &operator<<(std::ostream &os, const Matrix<T> &m) {
  for (size_t r = 0; r < m.rows(); ++r)
    for (size_t c = 0; c < m.columns(); ++c)
      os << m[r][c] << " \n"[c == m.columns() - 1];
  return os;
}
class TaskD {
 public:
  void solve(istream &cin, ostream &cout) {
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<int>> E(N);
    vector<int> T(N);
    cin >> T;
    for (int i = 0; i < M; ++i) {
      int u, v;
      cin >> u >> v;
      --u;
      --v;
      E[u].push_back(v);
      E[v].push_back(u);
    }
    vector2<double> D(N, N, 0);
    for (int u = 0; u < N; ++u) {
      for (int v : E[u]) {
        D[u][v] += 1.0 / E[u].size();
      }
    }
    auto relax = [&](int v) {
      if (D[v][v] > 1e-10) {
        for (int w = 0; w < N; ++w) {
          if (v != w) {
            D[v][w] /= (1 - D[v][v]);
          }
        }
        D[v][v] = 0;
      }
      for (int u = 0; u < N; ++u) {
        if (u != v && D[u][v] > 1e-10) {
          for (int w = 0; w < N; ++w) {
            if (w != v && D[v][w] > 1e-10) {
              D[u][w] += D[u][v] * D[v][w];
            }
          }
        }
      }
      for (int u = 0; u < N; ++u) {
        D[u][v] = 0;
        D[v][u] = 0;
      }
    };
    for (int v = 0; v < N; ++v) {
      if (v != 0 && !T[v]) {
        relax(v);
      }
    }
    vector<double> Init;
    for (int u = 0; u < N; ++u) {
      if (T[u]) {
        Init.push_back(D[0][u] / (1 - D[0][0]));
      }
    }
    vector<vector<double>> Trans;
    relax(0);
    for (int u = 0; u < N; ++u) {
      if (T[u]) {
        Trans.push_back({});
        for (int v = 0; v < N; ++v) {
          if (T[v]) {
            Trans.back().push_back(D[u][v]);
          }
        }
      }
    }
    Matrix<double> A(Trans);
    auto L = A.power(K - 2).transpose() * Init;
    cout << fixed << setprecision(10) << L.back() << endl;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  TaskD solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}