Problem F
Cascade Centrality
Given an undirected graph $ G = (V, E) $, the cascade centrality of a node $ i \in V $ is defined as:
\[ 1 + \sum _{j \in V \setminus \{ i\} } \sum _{P \in P_{ij}} \frac{1}{\chi _P}, \]where $ P_{ij} $ is the set of all simple paths from node $ i $ to node $ j $, and the degree sequence product $ \chi _P $ of a path $ P $ is the product of the degrees of all nodes along the path, including the ending node but excluding the starting node.
Compute the cascade centrality of the given node, rounded to one decimal place. Your answer will be accepted if its absolute error is at most $ 0.1 $.
Input
-
The first line contains two integers $ N $ and $ M $ $(1 \le N \le 100,\ 1 \le M \le 150)$ — the number of nodes and edges in the graph.
-
Each of the next $ M $ lines contains two integers $ u_i $ and $ v_i $ $(1 \le u_i, v_i \le N)$, representing an undirected edge between nodes $ u_i $ and $ v_i $.
-
No node is connected to itself.
-
There is at most one edge between any pair of nodes.
-
-
The last line contains an integer $ x $ $(1 \le x \le N)$, the index of the node whose cascade centrality is to be computed.
Output
Print a single real number — the cascade centrality of node $ x $, rounded to one decimal place.
Note
All test cases are constructed so that the exact result is never exactly halfway between two representable values (e.g., $ x.y5 $), so rounding ambiguities do not arise. In particular, any reasonable implementation of rounding to one decimal place will produce an accepted result.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 7 1 2 1 3 1 4 2 3 3 4 3 5 4 5 1 |
3.2 |
