Problem: An undirected graph is given. Each edge of the graph disappears with a constant probability. Calculate the probability with which the remained graph is connected.



Input

The first line contains three integers N (1 \leq N \leq 14), M (0 \leq M \leq 100) and P (0 \leq P \leq 100), separated by a single space. N is the number of the vertices and M is the number of the edges. P is the probability represented by a percentage.

The following M lines describe the edges. Each line contains two integers v_i and u_i (1 \leq u_i, v_i \leq N). (u_i, v_i) indicates the edge that connects the two vertices u_i and v_i.

Output

Output a line containing the probability with which the remained graph is connected. Your program may output an arbitrary number of digits after the decimal point. However, the absolute error should be 10^{-9} or less.

Examples

Input

3 3 50
1 2
2 3
3 1


Output

0.500000000000


Input

3 3 10
1 2
2 3
3 1


Output

0.972000000000


Input

4 5 50
1 2
2 3
3 4
4 1
1 3


Output

0.437500000000

Solution (in CPP):

Solution:
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (1e+18) + 7;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

ll mod_pow(ll a, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%mod;
		a = a * a%mod; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

//const int max_n = 1 << 22;
//modint fact[max_n], factinv[max_n];
//void init_f() {
//	fact[0] = modint(1);
//	for (int i = 0; i < max_n - 1; i++) {
//		fact[i + 1] = fact[i] * modint(i + 1);
//	}
//	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
//	for (int i = max_n - 2; i >= 0; i--) {
//		factinv[i] = factinv[i + 1] * modint(i + 1);
//	}
//}
//modint comb(int a, int b) {
//	if (a < 0 || b < 0 || a < b)return 0;
//	return fact[a] * factinv[b] * factinv[a - b];
//}

int num[14][14];
int n, m; ld p;

ld dp[1 << 14];

ld pro[101];
int cnt[14][1 << 14];
void solve() {
	cin >> n >> m >> p; p /= 100.0;
	rep(i, 101) {
		pro[i] = 1;
		rep(j, i)pro[i] *= p;
	}
	rep(i, m) {
		int a, b; cin >> a >> b; a--; b--;
		num[a][b]++;
		num[b][a]++;
	}
	rep(i, n) {
		rep(j, (1 << n)) {
			rep(k, n)if (j&(1 << k))cnt[i][j] += num[i][k];
		}
	}
	dp[1] = 1;
	rep1(i, n-1) {
		vector<ld> cdp(1 << i,0);
		cdp[0] = 1;
		rep1(j, (1 << i)-1) {
			vector<int> b;
			int le = 0;
			per(k, i) {
				if ((j&(1 << k)) == 0)b.push_back(k);
				else le = k;
			}
			int len = b.size();
			rep(x, (1 << len)) {
				int le2 = 0;
				int pre = 0;
				per(y, len) {
					if (x&(1 << y)) {
						le2 = b[y]; pre |= (1 << b[y]);
					}
				}
				//if (le2 <= le) {
					int sum = 0;
					rep(y, len)if (x&(1 << y))sum += cnt[b[y]][j];
					cdp[pre | j] += cdp[pre] * dp[j] * pro[sum] * (1 - pro[cnt[i][j]]);
				//}
			}
		}
		rep(j, (1 << i)) {
			dp[j ^ (1 << i)] = cdp[j];
		}
	}
	cout << dp[(1 << n) - 1] << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(12);
	//init_f();
	//int t; cin >> t; rep(i, t)solve();
	//while (cin >>n>>m>>s>>t, n)solve();
	solve();
	stop
		return 0;
}