Let \(cnt(S)\) be the number of edges \((x,y)\) where \(x\in S\) and \(y\in S\). Let \(f(S)\) be the number of ways to choose edges \((x,y)\) where \(x\in S\) and \(y\in S\) such that \(S\) form a connected component.

\(cnt\) can be computed in \(O(2^nm)\) time.

Let \(x\) be any vertex in \(S\). If \(S\) is not a connected component,, there must be another connected component \(T\subset S\) and \(x\in T\). Enumerating \(T\) we get the transition

\[f(S)=2^{cnt(S)}-\sum_{x\in T,T\subset S} f(T)2^{cnt(S-T)}\]

The answer for vertex \(x\) can be computed as follows: we enumerate the connected component with \(1,x\).

\[ans(x)=\sum_{1\in S,x\in S} f(S) 2^{cnt(\{1,2,...,n\}-S)}\]

Time complexity: \(O(3^n+2^nn^2).\)