There is no such \(X\) if and only if both of the following conditions hold:

• \(G\) is bipartite.
• For each vertex \(v\), classify the edges incident to \(v\) according to which \(2\)-vertex-connected components they belong to. Let \(c_1, c_2, \dots, c_n\) be the sizes of these groups. Then, it is possible to form every integer from \(0\) to the degree of \(v\) (\(= c_1 + c_2 + \dots + c_n\)) as a sum of some of these \(c_i\).

Assuming this, let us solve the decision problem. We can check \(2\)-vertex-connectedness in \(O(N + M)\) time. For the second condition, we can decompose the graph into \(2\)-vertex-connected components using a low-link method in \(O(N + M)\) time, thus obtaining the \(c_1,c_2,\dots,c_n\) for each vertex \(v\). For deciding whether every integer from \(0\) to \(c_1 + c_2 + \dots + c_n\) can be formed by some subset, it can be shown by induction that it is necessary and sufficient that \(c_{i+1} \leq c_1+c_2+\dots +c_i + 1\) for all \(i\) where \(c_1 \leq c_2 \leq \dots \leq c_n\). We can do this in \(O(M \log M)\) time, with sorting being the bottleneck. Therefore, the problem is solved in \(O(N + M \log M)\) time.

Now, we prove that the conditions are indeed necessary and sufficient. We start with necessity.

Necessity

For the first condition, consider \(X = (0,0,\dots,0)\). If there is an odd cycle, it is impossible to orient the edges in a way that satisfies the requirement, so \(G\) must be bipartite.

For the second condition, fix a vertex \(v\). Suppose \(X_u = 0\) for all \(u \neq v\). Determine which \(X_v\) values allow a valid orientation of edges. For any two distinct neighbors \(a\) and \(b\) of \(v\), if there is a simple cycle passing through \(v,a,b\), then the orientations of edges \((v,a)\) and \((v,b)\) must match. Hence, the edges from \(v\) are classified by the \(2\)-vertex-connected components they belong to, and it is necessary that one can produce any integer from \(0\) to \(c_1 + c_2 + \dots + c_n\) as a sum of some subset of \(c_1, \dots, c_n\).

Sufficiency

First, consider the case \(G\) is a tree. Let us observe that the conditions are satisfied, and one can provide an orientation for every possible \(X\). Root the tree arbitrarily and orient edges in the order from root to leaves. Focusing on a particular vertex \(v\), exactly those edges leading from \(v\) toward the root have already been oriented. You can then orient the remaining edges connected to \(v\) to make the in-degree or out-degree of \(v\) match \(X_v\) (for example, if \(X_v = 1\), orient the remaining edges in the opposite direction of the root-side edge).

In the general case, a similar method is possible because the \(2\)-vertex-connected components form a tree structure (the block-cut tree). The set of edges in a \(2\)-vertex-connected component corresponds to an edge in the tree case. To proceed similarly as in the tree case, those edges must be oriented uniformly at its endpoints, which is possible because \(G\) is bipartite.