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:
// haaaaaaaaaaaaard

#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	int n,m;
	double p; scanf("%d%d%lf",&n,&m,&p);
	p/=100;

	int e[1<<14]={}; // e[S] := ( S から V\S へ出ている辺の本数 )
	rep(i,m){
		int u,v; scanf("%d%d",&u,&v); u--; v--;
		rep(S,1<<n){
			if(S&1<<u && (S&1<<v)==0) e[S]++;
			if(S&1<<v && (S&1<<u)==0) e[S]++;
		}
	}

	// dp[S] := ( V の部分集合 S が連結になる確率 )
	// ここで、S と V-S のつながり方については気にしていない
	double dp[1<<14];
	dp[0]=1;
	rep(S,1<<n) if(S!=0) {
		// S に含まれる頂点(どれでもいい)を一つ固定する
		int u0;
		rep(u,n) if(S&1<<u) u0=u;

		// S を頂点集合とみた部分グラフに制限して考える。
		//   dp[S] = ( u0 を含む連結成分が S である確率 )
		// と
		//   Σ_{T \subset S, u0 \in T} ( u0 を含む連結成分が T である確率 ) = 1
		// より、移項して dp[S] についての漸化式
		//   dp[S] = 1 - Σ_{T \subset S, u0 \in T, T!=S} ( u0 を含む連結成分が T である確率 )
		// を得る。
		// さらに
		//   ( u0 を含む連結成分が T である確率 )
		// = ( T が連結になる確率 ) * p^k
		// = dp[T] * p^k, ( k は T と S\T の間にある辺の本数 )
		// なので
		//   dp[S] = 1 - Σ_{T \subset S, u0 \in T, T!=S} dp[T] * p^k
		// となる。
		dp[S]=1;
		for(int T=(S-1)&S;T>0;T=(T-1)&S) if(T&1<<u0) {
			dp[S]-=dp[T]*pow(p,(e[T]+e[S-T]-e[S])/2);
		}
	}

	printf("%.15f\n",dp[(1<<n)-1]);

	return 0;
}