Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Sereja has an undirected graph on N vertices. There are edges between all but M pairs of…

  1. User

    Sereja has an undirected graph on N vertices. There are edges between all but M pairs of vertices.

    A permutation p on the vertices of the graph is represented as p[1], p[2], … , p[N] such that for all i, p[i] is a vertex of the graph. A permutation is called connected if there is an edge between vertices p[i] and p[i+1] for all natural numbers i less than N. Sereja wants to know the number of connected permutations on the graph vertices. Input

    First line of input contains a single integer T, denoting the number of test cases. T tests follow. First line of each test case contains two integers, N and M. M lines follow, each containing a pair of indices of vertices, indicating that those vertices are not connected by an edge.

    Output

    For each test case, output one number — the answer for the problem modulo 10^9+7.

    Constraints

    1 ≤ T ≤ 10 1 ≤ N ≤ 10^5 0 ≤ M ≤ 7

    Example Input: 2 4 3 1 2 2 3 3 4 2 1 1 2

    Output: 2 0

  2. DeepSeek Assistant

    We need to count number of permutations p of N vertices such that for each consecutive pair (p[i], p[i+1]) there is an edge in the graph. Graph is complement of given missing edges. So essentially graph is almost complete, except M missing edges. M ≤ 7, N up to 1e5. So graph is dense.

    We need number of Hamiltonian paths (covering all vertices exactly once) in undirected graph? Actually a connected permutation is exactly a Hamiltonian path (order of vertices along a path that visits all vertices exactly once) such that each consecutive pair is adjacent. So we count the number of Hamiltonian paths (undirected) in this graph. However note that the graph is undirected; the permutation order matters: p[1] to p[N] is a sequence. So each path counted as a permutation (ordered sequence). Usually number of Hamiltonian paths counts directed paths (order matters) unless stated. So we count all permutations that form a path. That is number of Hamiltonian paths in an undirected graph. That's #P-hard in general, but with M ≤ 7 we can use inclusion-exclusion over missing edges.

    We have graph G = K_N minus missing edges set E_missing (size M). So we need number of permutations p of vertices [N] such that for all i, (p[i], p[i+1]) ∉ E_missing, i.e., they are adjacent in G. Since in complete graph, all pairs are edges, so any permutation works. So total permutations N! are valid in complete graph. But with missing edges, we need to exclude those permutations that contain at least one forbidden consecutive pair.

    Thus number of Hamiltonian paths = total permutations - those that have at least one missing edge as consecutive pair.

    But careful: In K_N, all edges exist, but we removed some edges; so in the graph, adjacency holds if the pair is not among missing edges. So a permutation is "connected" if for each consecutive pair, the pair is not in the forbidden set. So indeed it's the set of permutations avoiding M specific ordered patterns? But note: edges are undirected, so (u,v) same as (v,u). In permutation, consecutive pairs are ordered, but condition depends on unordered pair. So effectively, for each forbidden pair {a,b}, we cannot have a and b adjacent in the permutation (in either order).

    Thus we have constraints: For each forbidden pair {a,b}, p[i] and p[i+1] cannot be (a,b) or (b,a).

    So we need to count permutations of N elements avoiding adjacency of certain pairs. This is a classic problem of counting permutations with forbidden adjacent pairs, and can be solved using inclusion-exclusion over the set of forbidden pairs that appear as adjacent pairs. However, the forbidden pairs are specific; and there may be overlap (some vertices appear in multiple missing edges). Since M ≤ 7, we can use inclusion-exclusion over subsets of the missing edges, counting permutations where all edges in the subset are required to be present as consecutive pairs (i.e., they appear somewhere adjacent, but they could appear multiple times? Actually we want to count permutations that contain a particular set of forbidden pairs as adjacent pairs (at least those). In inclusion-exclusion, for a subset S of missing edges, we want to count permutations that contain all those edges as adjacent pairs (i.e., each pair in S appears at least once as consecutive elements in the permutation). But careful: In inclusion-exclusion to count permutations that avoid all forbidden adjacencies, we usually use:

    Number = sum_{S ⊆ E_missing} (-1)^{|S|} * f(S), where f(S) = number of permutations that contain all edges in S as adjacent pairs (i.e., satisfy for each edge in S, the two vertices are adjacent somewhere in the permutation). However, note that this standard formula holds when we want to count permutations that avoid a set of "bad" properties (each property is "edge e appears adjacent"). Then inclusion-exclusion over subsets of properties that are forced to occur. That works as long as we can compute f(S) = number of permutations where for each e in S, there is at least one occurrence of that e as a consecutive pair (maybe more). However, typical inclusion-exclusion for forbidden positions works if the events are independent? But they are not independent, but the formula holds: |A_1 ∩ A_2 ∩ ...| = N! - sum |A_i| + sum |A_i ∩ A_j| - ... where A_i is event that forbidden edge i appears. So f(S) = number of permutations that contain all edges in S (i.e., ∩_{i∈S} A_i). So we need to compute for any subset S of missing edges, how many permutations have the property that each of these unordered pairs appears as a consecutive pair somewhere.

    Now, given that M ≤ 7, we can enumerate all subsets (max 2^7=128) and compute f(S). N up to 1e5, so we need to compute f(S) efficiently.

    The problem reduces to: Given a set of unordered pairs S (with |S| ≤ 7), count permutations of N vertices such that for each {u,v} in S, the permutation contains u and v as consecutive neighbors (i.e., there exists i such that (p[i], p[i+1]) = (u,v) or (v,u)). Note that S may have overlapping vertices; also the same pair may appear multiple times? Not, S is set.

    We need to count permutations with prescribed adjacency constraints? This looks like counting permutations where some given pairs must be adjacent at least once. This is tricky because we need at least one occurrence, not exactly one. However, due to small S we can use inclusion-exclusion again? But we may be able to use a combinatorial counting via considering the structure of constraints: The set S of required adjacencies can be thought as a graph H on the N vertices (with edges S). The condition that each edge in S appears at least once as adjacent in the permutation. That is like requiring that the permutation "covers" each edge somewhere.

    Alternatively, we can treat each edge in S as requiring that u and v be consecutive. This is akin to forcing them to be "glued" together? But careful: In permutations where an edge must appear at least once, it could appear multiple times, but since permutation includes each vertex exactly once, a given unordered pair can appear at most once as consecutive pair? Actually can an unordered pair appear more than once as consecutive? In a permutation of distinct elements, the same unordered pair {u,v} can appear consecutively only if they appear multiple times? No, each vertex appears exactly once, so the pair {u,v} can be adjacent at most once (since u and v appear exactly once each, they can be neighbors at most at one position: if u is immediately before v or v before u). So each unordered pair can appear at most once as consecutive. Thus for a given edge e, it either appears (exactly once) or not in a permutation. Good! That simplifies: In a permutation, each unordered pair of distinct vertices appears at most once as consecutive (actually exactly one adjacency if they are adjacent, else none). So the events A_e are: e appears as consecutive (once). Since they are mutually exclusive? Not exactly mutually exclusive: two different edges can both appear, but they may share vertices? If they share a vertex, it's possible for both to appear, but the vertex would have two neighbors in the permutation, which is fine (each vertex can be adjacent to at most two neighbors in the linear order, except endpoints have one). However, if two edges share a vertex, say edges {a,b} and {a,c}, then for them both to appear, a must be adjacent to both b and c, which is impossible because in a permutation, a has only two neighbors (left and right) at most. So if both {a,b} and {a,c} appear as consecutive pairs, then a would need to be adjacent to b and c simultaneously, which is impossible because a can only have two adjacent positions; but it could be adjacent to b on one side and c on the other side. That is possible: a could have b on left and c on right, or vice versa. Then a would be adjacent to both b and c. So that is allowed. However, what about three edges sharing a vertex? a can be adjacent to at most two distinct vertices, so at most two edges incident to a can appear. So events can be conflicting if we require three edges incident to same vertex. That will be automatically accounted in counting permutations that satisfy all edges: If S contains more than two edges incident to the same vertex, then f(S) = 0 because impossible.

    Thus for a given S, we need to count permutations where for each {u,v} in S, u and v are adjacent (consecutive). This is essentially counting permutations where we force adjacency for a set of edges. Since each such edge must be adjacent exactly once (since at most once and at least once), it's a constraint that the permutation contains these adjacencies as subgraph. The permutation corresponds to a Hamiltonian path (linear ordering) on N vertices. The constraints say that certain edges must be present in the path. So we are counting Hamiltonian paths in K_N that include a specified set of edges S. But note that S is a set of edges (size ≤7). We need to count number of Hamiltonian paths (orderings) that contain all edges in S. And we treat the path as undirected? Actually the adjacency is undirected; if we require {u,v} be adjacent, then either order is allowed. So we are counting number of linear arrangements (permutations) where the unordered pairs of S are adjacent.

    Thus f(S) = number of Hamiltonian paths (with N vertices) that include all edges in S, i.e., the path's edge set must contain S as a subset. Since the graph is complete, any edge is allowed; we just need that the path uses these edges.

    So we need to compute number of permutations of N distinct vertices such that a given set of edges S (unordered) are all present as consecutive pairs.

    This is a combinatorial counting problem that can be handled by considering the structure induced by S: The edges in S define a graph on some vertices (only those involved). Since |S| ≤ 7, the number of vertices involved in S is at most 2|S| (but likely less due to overlaps). Let V_S be set of vertices that appear in S. Its size is at most 14 but often less.

    Now, a Hamiltonian path is an ordering of all N vertices. The constraints impose that certain pairs must be adjacent. This effectively forces certain vertices to be next to each other. If we treat each required adjacency as a forced bond, we can contract each such edge? But careful: If edges form a path structure, contraction yields chains. However, if edges form a cycle or branching, constraints may be impossible.

    Given that the required edges S must be a subset of the edges of a Hamiltonian path (which is a simple path covering all vertices). The path's edges form a spanning tree (actually a Hamiltonian path is a spanning tree of degree ≤2). So the required edges S must be a subset of a path's edges. This implies that the subgraph induced by S must be a linear forest (a disjoint union of paths) because a Hamiltonian path is a single path, so its edges form a path graph; any subset of those edges is a forest where each component is a path, and no vertex can have degree >2. In addition, the S edges must be such that they can be embedded in a single Hamiltonian path covering all N vertices, meaning that the S graph must be a collection of vertex-disjoint paths (i.e., each vertex degree ≤2). Additionally, the S graph can't contain a cycle (since a cycle would require degree 2 for all vertices, but then to extend to a Hamiltonian path covering all vertices, you'd have to break the cycle; but if S contains a cycle, it's impossible because the path would have to include all edges of the cycle, but a simple path cannot contain a cycle). Actually if S contains a cycle, then it's impossible to have a Hamiltonian path that includes all edges of the cycle, because a path is acyclic and can't contain a cycle as a subgraph (if you include all edges of a cycle, then you would have a cycle). So S must be acyclic and each component must be a path (not necessarily a single path, but each component is a path, i.e., no branching). Moreover, S cannot have a vertex with degree ≥3. So first, if S has any vertex with degree ≥3, f(S) = 0.

    Also, if S contains a cycle, it would imply every vertex in the cycle has degree 2, but the component is a cycle, not a path. So we need to check if S (as undirected graph) is a linear forest (disjoint union of paths). That is necessary.

    Now, assuming S is a linear forest, we need to count number of Hamiltonian paths on N vertices that contain all edges in S. That is: we have a set of fixed adjacencies; each such adjacency means that the two vertices must appear consecutively in the final ordering, in either order. The components of S are paths. Within each component (which is a path of length k (k edges) and k+1 vertices), the order of vertices along that path is forced up to reversal? Actually, if we have a set of required adjacencies that form a path: e.g., edges {a,b}, {b,c}. Then in the final permutation, these three vertices must appear such that a adjacent to b and b adjacent to c. That forces that these three vertices appear consecutively in the order a-b-c or c-b-a. So essentially, the component becomes a "block" of vertices that must appear together in a contiguous segment, with internal order either one direction or the reverse. If the component is a path of length L (L edges) with L+1 vertices, the vertices must form a contiguous block in the permutation, and the order is either the path direction or its reverse. So each path component becomes a super-vertex (block) with two possible orientations (except possibly for a single-edge component which also has two orientations? Actually an isolated edge {u,v} is a path of length 1: it forces u and v to be adjacent, but they could be u then v or v then u; they need to be consecutive, but they might have other vertices on either side; they just need to be next to each other. However, are they required to be contiguous as a block? Yes, if u and v are adjacent and no other required adjacency connects to them, then they must be consecutive, but there could be other vertices before u and after v, or before v and after u, etc. But that still means they are together as a pair; they are a block of size 2. So each component is a contiguous block because the required adjacencies chain them together: if we have edges a-b and b-c, then a must be adjacent to b and b to c, implying that these three are consecutive in some order. If there were a gap (e.g., a, b, X, c), then b and c would not be adjacent. So indeed all vertices in a connected component (via required edges) must appear consecutively as a block, with internal order consistent with the path orientation (two possible overall orders). This holds because the required edges connect them into a tree (actually a path). If the component is not a tree but a star? But we disallow degree >2, so it's a path. So yes, each component is a path, thus the vertices in that component must be contiguous in the permutation, and the order must follow the path (or reverse). We need to verify: If the component is a path of length 2: edges {a,b} and {b,c}. Consider a permutation: ... a, b, c ... That is contiguous block a,b,c. Could we have b, a, c? That would have a adjacent to b? Yes, b and a are adjacent (since order b,a), but then a and c are not required to be adjacent. But b and c are required to be adjacent; in b,a,c, b and c are not adjacent because a is between them. So that fails. So the only ways are either a,b,c or c,b,a. So indeed the block is contiguous and order is fixed up to reversal. For a single edge {u,v}, the block is two vertices consecutive, either u,v or v,u. So each component becomes a block that can be permuted in 2 ways (except maybe if the component is a single vertex? But S only includes edges, so component must have at least 2 vertices. But we may have isolated vertices not in V_S. Those are free.

    Now, after contracting each component into a block, we have to arrange these blocks (and the remaining free vertices) in a linear order to form a Hamiltonian path covering all N vertices. Additionally, there is no further restriction: any ordering of the blocks is allowed, as long as the blocks are contiguous internally (they are). However, we also must consider that the endpoints of each block (the ends of the path component) can be connected to neighboring blocks or free vertices. There is no restriction on adjacency between blocks beyond that they are adjacent in the permutation, which is fine.

    Thus the counting reduces: Given a set of "blocks" (each block is a set of vertices that must appear together consecutively with a specified order up to reversal), count the number of linear arrangements (permutations) of all N vertices that satisfy those internal contiguous constraints.

    This is like counting the number of ways to arrange N items where some items are grouped into ordered sequences with two possible directions. The total number of ways is: first, treat each block as a "super item" that has internal degrees of freedom (2 orientations). Suppose we have B blocks (each component from S) and also K free vertices (those not appearing in any required edge). Then total number of items to arrange is B + K. The number of permutations of these (B+K) distinct items is (B+K)!. Then multiply by internal orientations: each block contributes a factor of 2 (since two possible orders, unless the block is of size 1? but block size at least 2, so 2). However, is that correct? Let's think: The blocks are not labeled externally? Actually the blocks are comprised of specific vertices. When we treat each block as an item, we are effectively grouping the vertices. The count of permutations of the N vertices respecting that grouping (i.e., vertices within each group appear consecutively in a specified order up to reversal) is: number of ways to order the groups * product over groups of (number of allowed internal orders). But careful: If we treat groups as items, each ordering of groups yields a sequence where the groups appear as blocks. Then we need to decide the internal order for each group. That gives (B+K)! * (2^{B})? But are there any symmetries? The groups are distinct because they contain distinct vertices. So yes, groups are distinct items. So any permutation of the groups is valid. Also, the free vertices are singletons, each considered a group of size 1 with only 1 internal order. So total number is (number of ways to arrange the groups) multiplied by product over groups of (internal permutations consistent with required adjacencies). Since for each block (path component), internal arrangement must follow the path orientation. As argued, each path component of length L (L edges) has exactly 2 valid orderings (the path forward or backward). However, is that always true? For a component that is an isolated vertex? Not applicable. So factor 2 per component. So f(S) = (number_of_groups)! * 2^{#components}.

    But wait: We need to ensure that there is no additional constraints: the blocks themselves can be placed in any order. That yields a permutation that satisfies that all required adjacencies hold: within each block, the required edges are present. There is no requirement that any other adjacency (like between blocks) be anything, so it's fine. However, we must ensure that the blocks themselves are contiguous and that the internal ordering of the block indeed includes each required edge. Since we fixed the orientation to be one of the two that respects all edges, it's satisfied.

    But there is a subtlety: Could there be a permutation that satisfies all required edges but does not have each component as a contiguous block? Suppose we have two required edges {a,b} and {c,d} that are disjoint. In a permutation, we could have ... a, b, ... c, d ... That works. But could we have interleaving? e.g., a, c, b, d? Then a adjacent to b? No, a and b are not adjacent because c is between. So they wouldn't be adjacent, thus fails. So indeed, for disjoint required edges, the vertices of each edge must be adjacent to each other, but they could be separated by other vertices? No, if a and b must be adjacent, they must be consecutive. So they must be next to each other. So the two vertices of an edge form a contiguous pair. But could two pairs interleave? For a and b must be adjacent, and c and d must be adjacent. The order a, c, b, d: here a and b are separated by c, so not adjacent. So not allowed. Thus each required edge forces its two vertices to be consecutive, but they can be placed anywhere. However, they can be adjacent to each other and also adjacent to other vertices. The block notion for a component arises when multiple required edges share vertices, forming a chain. But if edges are disjoint, each forms a separate block of size 2. So indeed each component is a maximal connected set in the graph induced by S. So our grouping into components is correct.

    Thus f(S) = (number_of_groups)! * 2^{#components} if S is a linear forest (i.e., max degree ≤ 2 and no cycles). Otherwise f(S) = 0.

    But is there any scenario where a component that is a path can be placed in the permutation such that it is not contiguous? Consider a path of three vertices a-b-c (edges a-b and b-c). Must a,b,c be consecutive? Suppose we have permutation ... a, b, x, c ... This would give a-b adjacent (good), but b-c are not adjacent because x between. So fails. So indeed they must be consecutive. But could there be an arrangement where a and c are at the ends of the block and b is somewhere else? That would break adjacency. So they must be consecutive as a block. So yes.

    Thus f(S) = (number_of_groups)! * 2^{#components}, where groups = components of S (each is a set of vertices connected by required edges) plus singleton vertices not in any required edge. However careful: The singleton vertices (not appearing in S) are also groups of size 1. So total number of groups G = (#components of S) + (N - |V_S|). Since |V_S| is number of distinct vertices incident to edges in S. Then f(S) = G! * 2^{c}, where c = number of components (each component corresponds to a connected component of the graph (V_S, S) that has at least one edge; singletons from V_S? Actually if a vertex appears in S but as isolated? Not possible; any vertex in V_S belongs to some edge, so it is part of a component. So components of S are exactly the connected components of the graph with vertices V_S and edges S. They all have size at least 2 (since an edge gives at least 2 vertices). So c is number of such components.

    But is it possible that some component is just a single vertex? No, because S only includes edges, so each component has at least one edge, so at least 2 vertices.

    Thus G = c + (N - |V_S|). And f(S) = G! * 2^{c} mod MOD.

    We must verify this formula with examples.

    Consider N=4, M=3 missing edges: (1,2), (2,3), (3,4). So graph is K4 minus three edges that form a path 1-2-3-4? Actually missing edges are those not present. So the graph G has edges except these missing. So we need permutations where consecutive pairs are NOT among missing. That is permutations that avoid adjacency of (1,2), (2,3), (3,4). Let's test our approach: Use inclusion-exclusion on missing edges. Compute total permutations = 4! = 24. For each missing edge e, count permutations where that edge appears as consecutive: f({e}). For e={1,2}: count permutations where 1 and 2 are adjacent. That number is 2 * (4-1)! = 2 * 6 = 12? Actually general count for a specific pair being adjacent: treat pair as block: 2 orders, then arrange the block and the other 2 items: (3)! * 2 = 6*2=12. That matches. So f({1,2}) = 12. Similarly for {2,3} and {3,4} each 12.

    Now f({1,2},{2,3}): edges share vertex 2. This is a path: 1-2-3. So according to formula: |V_S|=3, c=1 component, groups = c + (N - |V_S|)=1 + (4-3)=2 groups: the component (size3) and the singleton vertex 4. So f = 2! * 2^1 = 22=4. Let's enumerate permutations of {1,2,3,4} where 1-2 and 2-3 are adjacent. Which permutations satisfy? They must have 1 and 2 adjacent and 2 and 3 adjacent. That implies 1,2,3 appear consecutively in order either 1-2-3 or 3-2-1. And vertex 4 can be anywhere (before, after, or between? But they must be consecutive block. So possible permutations: treat block [1,2,3] with two orientations, and then place 4 in one of 3 positions relative to block (before, between? Actually block is contiguous; positions: 4 can be before block, after block, or between? If block is contiguous, 4 cannot be inserted inside block because that would break adjacency. So there are exactly 2 (orientations) * 2 (positions: before or after) = 4? Wait, there are 2 orientations for block, and for each, 4 can be placed either at the left or right of the block (since block of 3 items and single item, total 4 items, the number of arrangements of two distinct groups (block and 4) is 2! = 2. So indeed 2 positions: block then 4, or 4 then block. That yields 22=4. Check manually: possible permutations: 1 2 3 4; 3 2 1 4; 4 1 2 3; 4 3 2 1. Are these valid? For 1 2 3 4: edges (1,2) adjacent, (2,3) adjacent yes. For 3 2 1 4: similarly. For 4 1 2 3: (1,2) adjacent, (2,3) adjacent. For 4 3 2 1: same. So 4 matches.

    Now f({2,3},{3,4}) similarly 4.

    f({1,2},{3,4}): edges are disjoint. Then |V_S|=4, components: two components each of size 2. c=2, groups = c + (N - |V_S|)=2 + (4-4)=2? Actually groups = components (2) + remaining vertices (0) = 2 groups. So G=2, f = 2! * 2^2 = 2 * 4 = 8. Let's enumerate: we have two blocks: {1,2} and {3,4}. Each block can be ordered in 2 ways. The two blocks can be ordered in 2! = 2 ways. So total 8 permutations. Indeed, they are: (1,2) then (3,4) in two orders each -> 4; plus (3,4) then (1,2) -> another 4. Check: e.g., 1 2 3 4, 2 1 3 4, 1 2 4 3, 2 1 4 3; then 3 4 1 2, 4 3 1 2, 3 4 2 1, 4 3 2 1. All satisfy both edges.

    Now f({1,2},{2,3},{3,4}) = S with three edges forming a path 1-2-3-4. That's a component of size 4 (path of length 3). c=1, |V_S|=4, groups = 1 + (4-4)=1 group. f = 1! * 2^1 = 2. So permutations where all three missing edges appear? Actually we need permutations where all three edges appear as adjacent. That would be permutations where 1-2, 2-3, 3-4 are all adjacent. That forces the ordering to be either 1-2-3-4 or 4-3-2-1. So indeed 2.

    Now we can compute inclusion-exclusion for the original problem: number of permutations avoiding these edges = total permutations - sum f({e}) + sum f({e1,e2}) - sum f({e1,e2,e3}) + ... with sign (-1)^{|S|}. For the given example, compute:

    N=4, M=3 missing edges set: E = {a,b,c} where a={1,2}, b={2,3}, c={3,4}.

    Total = 24. Sum over size1: f(a)+f(b)+f(c) = 12+12+12=36. Sum over size2: f(ab)+f(ac)+f(bc) = (edges share? ab = {a,b}? a and b share vertex so f=4; ac = {a,c}? a={1,2}, c={3,4} disjoint -> f=8; bc = {b,c} shares vertex -> f=4. Total = 4+8+4=16. Sum over size3: f(abc)=2. So inclusion-exclusion: 24 - 36 + 16 - 2 = 2. That matches example output 2.

    Great! So formula works.

    Now test second example: N=2, M=1 missing edge (1,2). So graph has no edge? Actually complete graph K2 has one edge (1,2). Missing that edge means graph has no edges. So connected permutations require edge between p[1] and p[2] but none exists, so answer 0. Our method: total permutations = 2! = 2. f({1,2}) = number of permutations where 1 and 2 are adjacent: all permutations are adjacent? In permutation of 2 elements, they are always adjacent (since only two positions). So f({1,2}) = 2. So inclusion-exclusion: 2 - 2 = 0. Works.

    Thus our inclusion-exclusion approach with f(S) computed as above is correct provided S graph is a linear forest; else f(S)=0.

    Now the challenge: For each test case, N up to 1e5, M ≤ 7. We need to compute sum_{S⊆E_missing} (-1)^{|S|} f(S) mod MOD (1e9+7). Since M ≤ 7, number of subsets is ≤128, which is trivial. We need to compute f(S) quickly per subset.

    So for each subset S, we need to:

    • Build the graph on vertices involved in S (maybe up to 14 vertices). But we need to check if S is a linear forest (max degree ≤ 2, no cycles). Also need to compute the number of components c, and the number of distinct vertices |V_S|. Then G = c + (N - |V_S|). Compute f(S) = factorial(G) * (2^c mod MOD) mod MOD. Also need factorial up to N (1e5) precomputed for all test cases (max N across tests up to 1e5, T up to 10, total N sum maybe up to 1e6, but we can precompute factorial up to max N across all test cases). Also need factorials modulo MOD.

    But careful: Is f(S) always (G!)*2^{c}? Let's re-evaluate in some edge cases:

    • S empty: then c = 0 (since no edges, there are no components). But what about components? We treat components as those with edges. So c = 0. |V_S| = 0. G = 0 + N = N. f(empty) = N! * 2^0 = N! = total permutations. Good.

    • S with one edge: then graph has two vertices, one edge, c=1, |V_S|=2, G = 1 + (N-2) = N-1. f = (N-1)! * 2. Usually number of permutations where specific pair are adjacent is 2*(N-1)!. That matches because (N-1)! * 2 = 2*(N-1)!.

    • S with two disjoint edges: c=2, |V_S|=4, G = 2 + (N-4) = N-2. f = (N-2)! * 4. Let's check manually: number of permutations where two specific disjoint pairs each are adjacent. We can treat each pair as a block; two blocks plus remaining N-4 singletons: total groups = (N-4) + 2 = N-2. The number of arrangements of these groups: (N-2)!; each block has 2 orientations: total 2^2 * (N-2)!. That matches.

    • S with two edges sharing a vertex: path of length 2. Then c=1, |V_S|=3, G = 1 + (N-3) = N-2. f = (N-2)! * 2. Let's verify: block of three vertices (path) with 2 orientations, plus remaining N-3 singletons: groups = 1 + (N-3) = N-2. Arrangements: (N-2)! * 2. That seems plausible. But is there any possibility where the block is placed but the internal order is not strictly one of the two orientations? Could there be permutations where the three vertices appear as 2,1,3? That would give adjacencies: (2,1) satisfies first edge, but (1,3) is not second edge. So fails. So indeed only 2.

    • S with a cycle? e.g., three edges forming a triangle. Then each vertex degree 2, but graph is a cycle. Is it possible to have a Hamiltonian path that includes all three edges? Let's test N=3, S = triangle (3 edges). Hamiltonian path on 3 vertices must have exactly 2 edges; cannot include all 3 edges because a path of length 2 uses 2 edges, while triangle has 3 edges. So impossible. So f(S)=0. According to our condition: max degree ≤2 passes (each vertex degree 2), but there is a cycle. We need to check for cycles. Since a Hamiltonian path is a tree, if S contains a cycle, it's impossible. So we must detect cycles. However, if S is a cycle but also includes extra vertices? But with ≤7 edges, cycle detection is needed.

    • S with a vertex degree >2: impossible.

    • S with a self-loop? Not possible.

    • S with multiple edges? Not.

    Thus algorithm for each subset S:

    1. Let edges = list of missing edges (given). But careful: In inclusion-exclusion, S is a subset of the missing edges. But we are counting permutations where those missing edges are present as adjacent pairs. That's fine.

    2. Build a graph on vertices that appear in edges of S. Since M ≤7, |S| ≤7, we can just use adjacency list for up to 14 vertices but we can map vertices to indices using a map/dictionary.

    3. Compute degree of each vertex. If any degree > 2, f(S) = 0.

    4. Check for cycles: Since degrees ≤2, each component is either a path or a cycle. We need to detect if any component is a cycle (i.e., all vertices in component have degree 2, and number of edges in component equals number of vertices). But also could be a component with a single edge (path). So for each component, we can traverse; if we encounter a component where every vertex has degree 2 and it is connected and has at least 3 vertices? Actually a cycle of length 2 would be two vertices with two edges between them? That would be parallel edges; not possible since S is a set (no multiedge). So a cycle would have at least 3 vertices. So we can detect: if component has number of edges == number of vertices (and all vertices degree 2), then it's a cycle. But simpler: Since max degree 2, a component is a cycle if and only if it is connected and each vertex has degree exactly 2. So we can check per component: if all vertices have degree 2, then it's a cycle. In that case f(S)=0.

    5. Also need to ensure no self loops? Not applicable.

    Thus if passes, we compute:

    c = number of connected components in the graph (i.e., number of components formed by edges). But careful: Could there be isolated vertices in V_S? Actually V_S includes only vertices incident to edges, so each vertex belongs to some edge, so they are all in components. So c is simply the number of connected components of the graph (V_S, S). However, if there is an isolated vertex? Not possible. So c = number of components.

    |V_S| = number of distinct vertices in S.

    G = c + (N - |V_S|).

    Then f(S) = fact[G] * pow2[c] % MOD, where fact[n] = n! mod MOD, and pow2[c] = 2^c mod MOD.

    Now we must precompute factorials up to max N across test cases, which is ≤1e5 (maybe 1e5 per test). Also precompute powers of 2 up to M (max 7) but c can be up to number of components, which max is |S| (if all edges disjoint). Since |S| ≤7, c ≤7. So we can compute pow2 on the fly.

    Edge Cases: N can be as large as 1e5. For S large, G could be N - |V_S| + c. Since |V_S| >= 2 (if non-empty) and c at most |S|, G can be up to N (for empty). So factorial up to N is needed.

    Now we must compute sum_{S ⊆ missing_edges} (-1)^{|S|} f(S). Since M small, straightforward.

    But we must be careful: The inclusion-exclusion formula as described counts permutations that avoid all missing edges as adjacency. However, we must ensure that we are counting permutations where consecutive pairs are edges in G (i.e., not missing). Indeed event A_e is "missing edge e appears as consecutive pair". So number avoiding all A_e = total - ... So that gives correct answer.

    But is there any nuance about multiple occurrences? Since each unordered pair can appear at most once, it's fine.

    Thus solution seems simple.

    But wait: Are there any permutations where a missing edge appears more than once? No, as argued.

    Thus algorithm:

    For each test case:

    • Read N, M.
    • Read M pairs (u,v). Since N up to 1e5, vertices numbered from 1 to N.
    • Store missing edges list: missing_edges = [(u_i, v_i) for i in range(M)].
    • Precompute factorials up to N (maybe up to max N across tests globally).
    • Precompute answers per test: ans = 0.
    • Loop over mask from 0 to (1<<M)-1:
      • edges_subset = edges indicated by mask.
      • Determine if subset is valid (no vertex degree >2, no cycles).
      • Compute |V_S| and c.
      • Compute G = c + (N - |V_S|)
      • f = fact[G] * (1 << c) % MOD (since c <=7, 2^c small)
      • if |S| % 2 == 1: ans = (ans - f) % MOD else ans = (ans + f) % MOD.
    • Print ans.

    Complexities: O(T * 2^M * (M + something)). Since M ≤ 7, 128 * small = trivial.

    Potential pitfalls:

    • Vertex indices can be up to 1e5, but we only need to handle vertices in subset. We can map each vertex that appears to a small index for degree and graph traversal. Use dictionary.
    • Cycle detection: Since degrees ≤2, we can just iterate over vertices, mark visited, and traverse. For each component, count vertices and edges (or simply check if any vertex has degree 2 and we come back to start). But we also need to ensure that there is no component that is a cycle. A component is a cycle if it is connected, each vertex degree exactly 2. So while traversing, we can compute number of vertices in component and check if all have degree 2. If yes and the component has at least 3 vertices? Actually a component with two vertices and each degree 2 would require two parallel edges between them (since each vertex would need two incident edges in the component, but there is only one edge between them because S is set; so can't have degree 2 on both with one edge. So with simple graph, a component of size 2 and both degree 2 is impossible. So it's safe: if all vertices in component have degree 2, it must be a cycle of length >=3. So we can just check for any component with all vertices degree 2, then invalid (f=0).
    • But what about a component that is a single edge? That's fine; degrees: one vertex degree 1, other degree 1.
    • What about a component that is a path of length >1: endpoints degree 1, internal vertices degree 2. That's allowed.

    Thus detection: If any vertex degree > 2 -> invalid. Else, for each component, if we encounter a vertex with degree 2 and after traversal, we find that the component is a closed loop (i.e., we traverse and return to start without hitting a degree-1 vertex) and all vertices degree 2, then it's a cycle and invalid. However, consider a component that is a path where all internal vertices degree 2 but endpoints degree 1, so not all vertices degree 2. So we only need to invalidate if there exists a component with no vertex of degree 1, i.e., all vertices degree 2. In a finite simple graph with max degree 2, a component with all vertices degree 2 is necessarily a cycle. So we can check: For each component, if it has at least one vertex with degree 1, then it's a path (or isolated? but no isolated vertices). If all vertices degree 2, invalid.

    But be careful: There is also the possibility of a component that is a single vertex with no edges? Not in V_S.

    Thus algorithm:

    For each subset S:

    • Create a map: vertex -> list of neighbors (only within S). Actually we just need degrees and to traverse. Since S size small, we can just store edges as pairs.

    Simplify: We can treat the graph on the vertices that appear in S. Build adjacency as a dict of sets or lists. Since at most 14 vertices, we can just list edges.

    Pseudo:

    def compute_f(N, edges_subset): if not edges_subset: return fact[N] # empty # collect vertices and degrees deg = {} adj = {} for (u,v) in edges_subset: deg[u] = deg.get(u,0)+1 deg[v] = deg.get(v,0)+1 adj.setdefault(u, []).append(v) adj.setdefault(v, []).append(u) # check degree >2 for d in deg.values(): if d > 2: return 0 # Now find components and check for cycles. visited = set() components = 0 for v in deg.keys(): if v in visited: continue # BFS/DFS from v stack = [v] visited.add(v) has_degree1 = False while stack: x = stack.pop() if deg[x] == 1: has_degree1 = True for nb in adj[x]: if nb not in visited: visited.add(nb) stack.append(nb) if not has_degree1: # all vertices in this component have degree 2 => cycle return 0 components += 1 # at this point, valid V = len(deg) # |V_S| G = components + (N - V) f = fact[G] * pow2[components] % MOD return f

    But careful: The 'has_degree1' check: In a component that is a path, there will be at least two vertices of degree 1 (unless it's a single edge? Actually a single edge: both vertices degree 1, so has_degree1 true). So that works. For a cycle, all degrees are 2, so has_degree1 false. So return 0.

    Edge case: Could there be a component that is a single vertex? Not possible because deg only includes vertices that appear in edges. So all vertices have at least degree 1. So fine.

    Now, an important nuance: The formula f(S) = G! * 2^c assumes that each component (path) can be oriented in exactly 2 ways. But is that always correct? For a component that is a single edge, there are indeed 2 ways: (u,v) or (v,u). For a longer path, also 2 ways (reverse order). But what if the component is a path of length 0? Not applicable. So yes.

    But is there any scenario where a component is a path but the orientation is not exactly 2? For example, consider a component that is a path of two edges: vertices a-b-c. The valid permutations for the block are: a,b,c and c,b,a. That's 2. No other orders preserve both adjacencies. So fine.

    Thus algorithm appears correct.

    Now double-check with more complex subsets: S may have multiple components, some of which are paths of varying lengths. The internal orientation factor for each component is 2. So product 2^c.

    Now the final answer is computed as inclusion-exclusion over subsets of missing edges. However, note that we are counting permutations that avoid any missing edge as adjacency. But is that the same as connected permutations? Yes, because graph is complete except those missing edges. So condition is exactly that each consecutive pair is not in missing set.

    Thus answer = sum_{S ⊆ missing} (-1)^{|S|} f(S).

    Now we should test with some random small cases to ensure.

    But let's also consider potential overcount? Inclusion-exclusion should be correct.

    Now we should think about the possibility of multiple missing edges being the same? Input says M lines each containing a pair; they might be duplicate? Probably not, but if duplicates, we need to handle: In graph, missing edges set is a set, duplicates don't matter. But input could have duplicate lines? Unlikely, but we can treat edges as set to avoid double counting. However, constraints may not guarantee distinctness. Safer: store as list but if duplicates exist, then the same missing edge appears twice; then inclusion-exclusion over subsets of M lines would treat them as separate properties, which would be wrong because they represent the same missing edge; but events would be identical and the inclusion-exclusion would overcount? Actually if there are duplicate entries, that would mean the same pair is listed twice as missing; but in the graph, it's just missing that edge; the property "edge e appears as consecutive" is a single property, not two separate properties. So we must treat missing edges as a set (distinct pairs). If input includes duplicates, we should deduplicate. But is it allowed? Problem statement: "M lines follow, each containing a pair of indices of vertices, indicating that those vertices are not connected by an edge." It doesn't say pairs are distinct, but logically they should be; but to be safe, we can read pairs and store them in a set to eliminate duplicates, and then M becomes the size of that set. However, M ≤ 7, so it's fine. But the input example does not have duplicates. We'll assume no duplicates; but we can add dedup just in case.

    Now another nuance: vertices are labeled 1..N. The graph is undirected, so pair (u,v) is same as (v,u). In input, they might be given in any order. We should treat as unordered.

    Now, check with an example where missing edges cause constraints that cannot be satisfied due to S containing a cycle: Suppose N=3, missing edges = {(1,2), (2,3), (1,3)}. That's all three edges missing; graph has no edges. Connected permutations require each consecutive pair to be an edge, but there are none, so answer = 0. Let's compute via inclusion-exclusion:

    Total permutations = 6. f({1,2}) = 2*(3-1)! = 22! = 4? Actually N=3: permutations where 1 and 2 adjacent: treat as block: 2 orientations * (2)! = 22=4. But let's list all 6 permutations of 1,2,3: 1,2,3 (adjacent 1-2 ok, 2-3? but not required for event A_{1,2} only) 1,3,2 (1-2 not adjacent) 2,1,3 (adjacent) 2,3,1 (2-1? adjacent? 2 and 1 are not consecutive; 2,3,1: consecutive pairs (2,3) and (3,1); 1 and2 not adjacent) 3,1,2 (1-2 not adjacent) 3,2,1 (2-1 adjacent? 3,2,1 has 2 and 1 adjacent). So four with 1-2 adjacent: 123, 213, 321, 231? Wait check: 2,3,1: 2 and 1 not adjacent. 3,2,1: 2 and 1 adjacent. So 123, 213, 321, ? actually 132? 1,3,2 no. 312? 3,1,2 no. 231? 2,3,1 no. So maybe only 3? Let's compute properly: permutations where 1 and 2 are consecutive. List all permutations of {1,2,3}: 1,2,3 -> yes (1-2) 1,3,2 -> no (1 and 2 separated by 3) 2,1,3 -> yes (2-1) 2,3,1 -> no (2 and 1 not adjacent) 3,1,2 -> no (1 and 2 separated by 1? Actually 3,1,2: consecutive pairs (3,1) and (1,2) => 1 and 2 are adjacent! Wait 3,1,2: positions: first 3, second 1, third 2. The consecutive pairs are (3,1) and (1,2). So 1 and 2 are adjacent. So yes. I missed that. So 3,1,2 has 1-2 adjacent. Similarly 3,2,1: pairs (3,2) and (2,1) => 2-1 adjacent. So also 3,2,1 yes. Let's list all: 123 yes 132 no (1-2? Actually 1,3,2: pairs (1,3) and (3,2) => 2 not adjacent to 1) 213 yes (2,1,3) 231? 2,3,1: pairs (2,3) and (3,1) => 1 not adjacent to 2) 312? 3,1,2 yes 321 yes (3,2,1) Thus 4 permutations: 123,213,312,321. So f=4, which is 2*(2)! = 4. Good.

    Similarly f({2,3})=4, f({1,3})=4.

    Now f({1,2},{2,3}) = for N=3, S edges share vertex; it's a path 1-2-3. Then f =? According to formula: |V_S|=3, c=1, G = 1 + (3-3)=1, f = 1! * 2 = 2. Indeed permutations that have both edges: only 1-2-3 and 3-2-1, i.e., 123 and 321. So 2.

    f({1,2},{1,3}) = edges share vertex 1, degree of 1 would be 2 (ok), but it's a "V" shape: edges {1,2} and {1,3}. This graph is not a path because vertex 1 has degree 2 but vertices 2 and 3 have degree 1, but it's actually a star of degree 2 (just two edges sharing a center). Is this a linear forest? The component is a tree with a vertex of degree 2 and two leaves; it's a path? Actually a path of length 2 would be 2-1-3. That's exactly the same: vertices 2-1-3 form a path. Indeed the edges {1,2} and {1,3} form a path of length 2 if we consider the order 2-1-3. So it is a path! Because a path is defined as a tree where max degree ≤2. In this graph, vertex 1 has degree 2, vertices 2 and 3 degree 1, so it's a path (specifically, the path 2-1-3). So it's allowed. But is it possible for a Hamiltonian path to include both edges {1,2} and {1,3}? For a permutation of 3 vertices, the only Hamiltonian path covering all vertices uses exactly two edges. If we include both edges, the set of edges in the path must be exactly {1,2} and {1,3}? But then the path would have vertex 1 adjacent to both 2 and 3, so the path would be either 2-1-3 or 3-1-2. That indeed includes both edges. So it's valid. So our condition that max degree ≤2 and no cycles correctly accepts this as valid (since it's a path). However, note: In our earlier definition, we required that S be a linear forest, i.e., each component is a path. The component with edges {1,2} and {1,3} is indeed a path (2-1-3). So it's fine. So our detection method: degree of vertex 1 = 2, degrees of 2,3 = 1. That passes degree ≤2. For component, we check if it has a vertex with degree 1 (has_degree1 true). Since there are degree-1 vertices, it's a path, not a cycle. So valid. So f = (N - |V_S| + c)! * 2^c = (3-3+1)! * 2 = 1! * 2 = 2. Good.

    Now f({1,2},{2,3},{1,3}) = triangle. degrees all 2. No vertex degree 1. So invalid -> f=0.

    Now inclusion-exclusion: ans = 6 - (4+4+4) + (2+2+2) - 0 = 6 -12 +6 =0. Good.

    So matches.

    Now consider N=4, missing edges set = something that leads to complicated overlapping. Our approach seems solid.

    Now, we need to consider the possibility that the graph's missing edges could be up to 7, but N is huge. Our formula f(S) depends on N via factorial of G. Since G = N - |V_S| + c, and |V_S| can be up to 2|S| (max 14) but might be less. So we need factorial up to N (since G up to N). That's fine; we can precompute factorial up to max N across test cases. Since N up to 1e5, we can precompute up to 100000 (maybe 100000 + a little). Also compute factorial mod MOD.

    Now, we need to compute pow2[c] mod MOD. Since c ≤ 7, just compute 1<<c mod MOD, but use modular arithmetic.

    Now, we need to ensure that we compute f(S) correctly when there are multiple components but some components might be isolated? Not possible.

    Potential oversight: The permutation orientation factor for each component is 2, but what if a component is a single vertex? That would be 1 orientation, but we don't have such components because we only consider vertices in S. So c counts only components that have at least one edge. However, what about vertices that are not in any edge (free vertices)? They are separate groups of size 1, each with 1 orientation. So overall, the groups are: each component (path) and each free vertex. So total groups = c + (N - |V_S|). That matches.

    But is there any scenario where a component (path) could be placed in the permutation in a way that the block is not contiguous? We argued no because required edges force adjacency along the chain, thus they must appear consecutively. However, consider a path component of length 2 (three vertices a-b-c). Could we have permutation where these three appear not consecutively but still have edges a-b and b-c adjacent? For a-b adjacency, a and b must be consecutive. For b-c adjacency, b and c must be consecutive. If a and b are consecutive, and b and c are consecutive, then the three must be consecutive, because b is adjacent to both a and c, so the order must be a,b,c or c,b,a. In either case, they are consecutive as a block. So yes.

    Now, what about components with a single edge: they must be consecutive, but they could be separated from other vertices? They are a block of two, but that block can be placed anywhere among other groups.

    Now, what about the case where the required edges form a path, but the path could be "wrapped" around due to the permutation being a cycle? No, it's a linear path.

    Thus formula holds.

    Now, we must consider that the inclusion-exclusion over missing edges S counts permutations where each edge in S appears as adjacency. However, if S contains edges that are not disjoint or not a linear forest, f(S)=0, which is consistent with the counting (since no permutation can contain those edges). Good.

    Now, we should also think about the possibility of permutations that contain a missing edge more than once? Already argued impossible.

    Thus algorithm is correct.

    But wait: Is there any subtlety about the graph being undirected and the permutation's adjacency condition is directed? We already considered that {u,v} adjacency can be either order. In counting f(S), we treat the block orientations as 2 for each component, covering both orders. That's correct.

    Now, check the example: Input 2 gave outputs 2 and 0. That matches.

    Now, we need to implement.

    Implementation details:

    • Read T.

    • Determine max N across test cases to precompute factorials up to that max. Since N up to 1e5 per test, we can precompute up to 100000 (or maybe 100005) once. But T up to 10, and N may vary; we can compute factorial array up to maximum N among tests to avoid recomputation. So first read all test cases? Alternatively compute up to 1e5+7 always. Simpler: precompute factorial up to 100000 (or maybe 100000+10) globally.

    • For each test:

      • Read N, M.
      • missing_set = set()
      • for i in range(M): read u,v if u>v: maybe sort to keep unordered; ensure that pair is stored consistently. Use tuple (min(u,v), max(u,v)). missing_set.add((u,v)).
      • Convert to list missing_edges = list(missing_set). Update M = len(missing_edges) (since duplicates may be removed). But note that M given may be up to 7, after dedup still ≤7.
      • Precompute ans = 0.
      • For mask in range(1<<M): edges_subset = [missing_edges[i] for i in range(M) if mask>>i & 1] f = compute_f(N, edges_subset) if popcount(mask)%2==1: ans = (ans - f) % MOD else ans = (ans + f) % MOD
      • Print ans.

    Now, compute_f must be fast but it's fine.

    Now, test on some random small N and M to verify manually. We can also reason about correctness more formally.

    But there is an alternative viewpoint: This is counting Hamiltonian paths in the complement of a small set of missing edges. Could also be solved via inclusion-exclusion on the missing edges as we did.

    Now, we need to be careful about modulo operations: ans may be negative after subtraction, so add MOD before output.

    Now, confirm that factorial[G] is defined for G up to N; G may be 0? If N=1? Then what is connected permutation? For N=1, there is a single vertex permutation; condition "for all i less than N, there is an edge between p[i] and p[i+1]" for i from 1 to N-1; if N=1, there are no i, so vacuously true. So answer should be 1. Let's see our method: Graph on 1 vertex with no edges (since no self-loops needed). Missing edges M can be 0 or maybe some? But missing edges only between distinct vertices, so M=0. Then total permutations =1! =1. So ans=1. Good. For N=1, M could be >0? M ≤7, but there are no pairs of distinct vertices, so M must be 0. So fine.

    For N=2, if M=0, graph is complete (edge exists). Then total permutations 2, both have consecutive pair edge, so answer 2. Our method: total=2, no subsets, ans=2. If M=1 missing edge, answer 0 as before.

    Now, what about N=3, M=0: total permutations =6, all have all consecutive pairs edges? Wait graph is complete, so any permutation works: 6. Check: In K3, every permutation yields edges (1,2) and (2,3) which are present because all edges exist. So answer 6. Inclusion-exclusion: only empty set, f(empty)=6. Good.

    Now, test a case where missing edges cause some permutations to be invalid but not all: N=4, missing edges only (1,2). Then answer should be total permutations minus those where 1 and 2 are adjacent. So total 24, f({1,2})=2*6=12, answer =12. Let's see if inclusion-exclusion gives 24-12=12. Good.

    Now, test with overlapping missing edges: N=4, missing edges: (1,2), (1,3). So graph missing edges from 1 to 2 and 1 to 3; all other pairs present. We need permutations where consecutive pairs are not (1,2) nor (1,3). Count manually? Could be done. Our method: M=2, subsets: empty:24; {1,2}:12; {1,3}:12; {1,2,1,3}: that's two edges, S size 2. Compute f for S = {(1,2),(1,3)}. This graph: vertices {1,2,3}, edges: 1-2,1-3. This is a path 2-1-3 (component with c=1, |V_S|=3, G=1+(4-3)=2, f=2! *2=4). So inclusion-exclusion: 24 -12 -12 +4 = 4. So answer=4. Let's manually verify: permutations of 4 where 1 is not adjacent to 2 nor to 3. So 1 cannot be next to 2 or 3. So 1 can only be adjacent to 4 (and also maybe endpoints? Actually in a permutation, each vertex (except endpoints) has two neighbors. Vertex 1 must have neighbors only 4? Since it can't be adjacent to 2 or 3, its only possible neighbor is 4, but it can have at most two neighbors. Since there are 4 vertices, in a permutation, 1 will have either one neighbor (if at endpoint) or two neighbors (if in middle). It cannot be adjacent to 2 or 3, so the only allowable neighbor is 4. So 1 must be at an endpoint, and its only neighbor must be 4. So permutation must start or end with 1, and 4 must be next to it. Additionally, 2 and 3 can be arranged in the remaining two positions, but they must not be adjacent? Wait condition only forbids adjacency of 1 with 2 or 3; adjacency between 2 and 3 is allowed (since not missing). So possible permutations: We need 1 at one end, 4 adjacent to 1, and the other two positions filled with 2 and 3 in any order. So if 1 is first: then second must be 4, then remaining positions 2,3 in order (2,3 or 3,2) -> 2 permutations. If 1 is last: then previous must be 4, and first two are 2,3 in order -> 2 permutations. So total 4. That matches.

    Thus our method works.

    Now, consider missing edges with cycles: e.g., N=4, missing edges: (1,2), (2,3), (3,1). That's a triangle on vertices 1,2,3. Then we need permutations where no consecutive pair among these three. Inclusion-exclusion: subsets: compute f(S) for S with two edges that share vertex? It will be valid if max degree ≤2 and not cycle. For triangle, any two edges: say (1,2) and (2,3) is valid (path), f= (c=1, |V_S|=3, G=1+(4-3)=2, f=2!*2=4). Similarly for other two-edge subsets, each 4. For three edges: triangle, degree each =2, no degree-1 -> invalid f=0. So ans = total 24 - (f each single: three edges each 12) + (f each pair: three pairs each 4) - f(triangle)=0 => 24 -36 +12 =0? Actually 24 -36 = -12, +12 = 0. So ans=0. That suggests no valid permutations. Is that correct? Graph missing edges: 1-2,2-3,3-1 are missing; so among vertices 1,2,3, none are connected to each other; they only have edges to vertex 4. So graph is like a star from 4 to each of 1,2,3, plus no edges among 1,2,3. So we need Hamiltonian path on 4 vertices. Since vertices 1,2,3 are only connected to 4, any path must have 4 in the middle to connect them, but can we have a Hamiltonian path? Let's think: The graph is: 4 connected to 1,2,3; and no other edges. So it's a star with center 4. The number of Hamiltonian paths in a star with center 4 and leaves 1,2,3: In a star K_{1,3}, there are paths that start at one leaf, go to center, then to another leaf, then to the third leaf? But there is no edge between leaves, so after center, you can go to another leaf, but then from that leaf you cannot go to the third leaf because leaves are not connected. So you cannot have a Hamiltonian path covering all four vertices because after going from leaf to center to leaf, you are stuck; you would need to go from second leaf to third leaf, but no edge. So indeed there is no Hamiltonian path. So answer 0 is correct. Good.

    Thus method works.

    Now, consider missing edges: N=5, missing edges: (1,2), (2,3), (3,4), (4,5). That is a path of missing edges. Graph is complete except missing edges along a path 1-2-3-4-5. So we need permutations avoiding adjacency of consecutive numbers? Actually we need to avoid edges {1,2}, {2,3}, {3,4}, {4,5}. So many permutations will be invalid. Our inclusion-exclusion with M=4 (max 7) will compute. It should be computable. So algorithm seems good.

    Now, we need to be cautious about the case when missing edges S contain a component that is a path but also have extra constraints due to the fact that the block might have to be placed in a certain orientation relative to other blocks? Could there be any restrictions that arise from the fact that the Hamiltonian path must be simple and use all vertices? In our grouping model, we treat blocks as items and permute them arbitrarily. That yields all permutations that satisfy the required adjacencies because the required edges are internal to blocks, and there is no restriction on adjacency between blocks. However, is it possible that a permutation satisfies the required edges but does not correspond to a grouping into contiguous blocks as we assumed? We argued that each component must appear contiguously. But is it possible that a component (path) appears in the permutation not as a contiguous block but still each required edge is present? Consider component with three vertices a,b,c with required edges a-b and b-c. As argued, for a-b to be adjacent, they must be consecutive. For b-c to be adjacent, they must be consecutive. If a and b are consecutive, and b and c are consecutive, then a,b,c are consecutive in some order. The only possibilities: order a,b,c or c,b,a. In both cases, they form a contiguous block. So yes.

    What about a component that is two disjoint edges? They are separate blocks; each block must be contiguous, but the blocks themselves can be interleaved? No, because if we interleave, say permutation ... a, b, x, c, d ... then a,b are adjacent (good), c,d adjacent (good). But a and b are together, c and d together, but they are not interleaved: a,b appear together, c,d together. Could we have a, c, b, d? That would break a,b adjacency (a and c are not b). So interleaving not possible. So each component forms a contiguous block, and blocks are not interleaved. So indeed the permutation is a concatenation of blocks (components) and singletons in some order.

    Thus our counting is correct.

    Now, one more nuance: In a component that is a path, the two possible orientations are reverse of each other. But could there be cases where a component is a path but some orientations are not allowed because they cause a forbidden adjacency with another block? In our inclusion-exclusion counting f(S), we are counting permutations that contain S edges (i.e., satisfy those adjacencies) regardless of other adjacencies. Since we are not imposing any restrictions on other pairs (they can be anything, including missing edges or not). In the inclusion-exclusion for the original problem, we are summing f(S) with sign; that is part of the formula. So for counting f(S), we do not care about other missing edges; they may appear or not; that's fine because inclusion-exclusion will later account for them. So within f(S), we must count all permutations that contain S edges, irrespective of whether they contain other missing edges. So our grouping and orientation counting is correct; we don't need to avoid missing edges.

    Thus all good.

    Now, consider computational details: For each subset, we need to compute degrees and check for cycles. Since M ≤ 7, we can implement simply.

    Potential performance: T up to 10, each with up to 128 subsets, each subset processing at most 14 vertices. So trivial.

    Now, we need to be careful about integer overflow: factorial array up to 100000 mod 1e9+7, fine.

    Now, implement.

    We'll precompute factorial[0..MAXN] and also maybe inv factorial if needed? Not needed.

    Pseudo-code:

    MOD = 10**9+7 MAXN = 100000 (maybe 100000+5)

    fact = [1]*(MAXN+1) for i in range(1,MAXN+1): fact[i] = fact[i-1]*i % MOD

    Then for each test case:

    def compute_f(N, edges): if not edges: return fact[N] deg = {} adj = {} for (u,v) in edges: deg[u] = deg.get(u,0)+1 deg[v] = deg.get(v,0)+1 adj.setdefault(u, []).append(v) adj.setdefault(v, []).append(u) for d in deg.values(): if d > 2: return 0 visited = set() components = 0 for v in deg: if v in visited: continue # traverse stack = [v] visited.add(v) has_degree1 = False # We'll also count vertices in component? not needed while stack: x = stack.pop() if deg[x] == 1: has_degree1 = True for nb in adj.get(x, []): if nb not in visited: visited.add(nb) stack.append(nb) if not has_degree1: return 0 components += 1 V = len(deg) G = components + (N - V) # compute 2^components mod MOD pow2 = 1 << components # components ≤7, safe as integer, but mod MOD f = fact[G] * (pow2 % MOD) % MOD return f

    But note: pow2 may be up to 2^7=128, but we can just compute and mod.

    Now, but careful: G may be up to N, and fact[G] is precomputed. But G can be up to N. Since factorial array up to MAXN (max N across tests) and we may compute fact for all indices, it's fine.

    Now, ensure that we compute fact up to the maximum N encountered. If we precompute up to 100000, that's enough.

    Now, test with example.

    Now, consider scenario where N is large (1e5) and subset S leads to G = N - |V_S| + c. That's fine.

    Now, what about the possibility that |V_S| may be 0 for empty set, we already handled.

    Now, what about the case where S contains edges that are not a linear forest but still possible? We argued impossible.

    Now, I think solution is correct.

    But wait, is there any subtlety about the graph being "undirected" and the permutation requiring adjacency? Our counting f(S) considered unordered adjacency constraints, which is fine.

    Now, confirm inclusion-exclusion: The standard principle: For a set of events A_i (i from 1 to M), the number of permutations that avoid all A_i is sum_{S ⊆ [M]} (-1)^{|S|} |∩_{i∈S} A_i|. Indeed that's what we use.

    Now, we need to ensure that our events A_i correspond to "missing edge i appears as consecutive pair". However, is it possible that a permutation contains a missing edge more than once? Not possible as argued. So events are "edge appears at least once". Good.

    Thus answer = ∑_{S⊆missing} (-1)^{|S|} f(S).

    Now, time complexity: O(T * 2^M * (M + |V_S|)) with |V_S| ≤ 2M ≤14, trivial.

    Now, test with some random small N and M to be thorough. But since we can't run here, we reason.

    Now, consider the case N=5, M=2 missing edges: (1,2) and (2,3). This is a path. Our inclusion-exclusion:

    total = 120 f({1,2}) = 2 * 4! = 48 f({2,3}) = 48 f({1,2},{2,3}) =? graph path 1-2-3, c=1, |V_S|=3, G=1 + (5-3)=3, f= 3! 2 = 62=12 Thus ans = 120 - 48 - 48 + 12 = 36.

    We can manually try to count permutations of 5 where 1 and 2 are not adjacent and 2 and 3 are not adjacent. Could verify perhaps.

    Now, check if any permutation may be double subtracted? Inclusion-exclusion should correct.

    Thus solution seems correct.

    Now, we need to think about if the problem asks for connected permutations. Could there be any other condition? The definition: "A permutation is called connected if there is an edge between vertices p[i] and p[i+1] for all natural numbers i less than N." So exactly what we used.

    Now, one nuance: The graph is undirected, but the edges are defined only between distinct vertices. There are no self-loops. Permutation p contains each vertex exactly once. So okay.

    Now, double-check constraints: M ≤ 7, so missing edges at most 7. N up to 1e5. So we can handle large N.

    Now, possible overflow: factorial array up to 1e5 is fine memory-wise.

    Now, ensure to use fast I/O for Python (since T up to 10, but only 128 subsets, so not heavy). But reading input with sys.stdin is fine.

    Now, about dedup: we should store missing edges as set of sorted tuples. Since M ≤ 7, dedup easy.

    Now, potential pitfall: When we compute f(S), we assume that each component corresponds to a block with exactly 2 orientations. But consider component that is a single edge: yes, 2 orientations. For component that is a path of length L, also 2 orientations (reverse). But is there any scenario where the component is a single vertex? No.

    Now, consider component that is a path but with possible symmetric orientations? No.

    Now, what about component that is a path but the vertices in the path may have some identical labels? No, distinct.

    Thus fine.

    Now, confirm the formula for f(S) with a more complex example: N=6, S contains two components: one is a path of 3 vertices (2 edges) and another is a single edge. Then c=2, |V_S|= (3+2)=5, G = 2 + (6-5) = 3. So f = 3! * 4 = 64=24. Let's try to manually count the number of permutations of 6 distinct vertices with these constraints: we have a block A of size 3 (say vertices a,b,c with edges a-b and b-c) and block B of size 2 (d,e with edge d-e). The remaining vertex f is free. So groups: block A (2 orientations), block B (2 orientations), and f. So total groups = 3. Number of arrangements of these 3 groups = 3! = 6. For each arrangement, orientation factors: 22=4. So total 24. Yes.

    Now, verify with a more intricate overlapping: S contains two edges sharing a vertex but also an edge disjoint? e.g., edges: {1,2}, {2,3}, {4,5}. This gives two components: component1 path 1-2-3 (c=1 for that? Actually components: one component with vertices 1,2,3 (connected via edges) and another component with vertices 4,5. So c = 2. |V_S| = 5. So G = 2 + (N-5). Works.

    Now, if there is a component that is a cycle, f=0.

    Now, check if any subset S may have a component that is a single vertex with a self-loop? Not possible.

    Thus algorithm done.

    Now, about modulo: Use MOD = 1000000007.

    Now, we should also consider the possibility of large N but G small? G can be as low as 0? Possibly if N = |V_S| - c? For example, if N = |V_S| - c? But N is total vertices, |V_S| ≤ 2|S| ≤14, c ≥1. So G = c + (N - |V_S|) = N - (|V_S| - c). Since |V_S| - c is number of vertices minus number of components. In a forest, |V_S| - c equals number of edges? Actually for a forest, number of edges = |V_S| - number_of_components (since each component tree: vertices = edges + 1, sum over components: |V_S| = edges_total + components => edges_total = |V_S| - components. In our case, edges_total = |S|. So |V_S| - c = |S|. So G = N - |S|. Interesting! Let's verify: For a forest (acyclic) where each component is a tree, we have sum over components (V_i - 1) = edges_total. So total vertices |V_S| minus number of components c = edges_total = |S|. Thus |V_S| - c = |S|. Indeed because each component with V_i vertices has V_i - 1 edges (since it's a tree; path is a tree). Since S is a set of edges with no cycles, it's a forest, so |S| = |V_S| - c. So G = c + (N - |V_S|) = N - (|V_S| - c) = N - |S|. That's a nice simplification! So for any valid S (forest with max degree ≤2, i.e., a linear forest), we have G = N - |S|. Because |V_S| - c = |S|. Let's test: For S empty: |S|=0, G = N - 0 = N. Works. For single edge: |S|=1, G = N-1. For two disjoint edges: |S|=2, G = N-2. For path of length 2: |S|=2, |V_S|=3, c=1, then |V_S|-c=2 = |S|, G = 1 + (N-3) = N-2. So yes! So f(S) = fact[N - |S|] * 2^{c}. That's simpler and avoids computing |V_S| and c separately? But we still need c for the factor 2^c, and also to check validity. But we can compute c from S as number of components in the forest. That is fine.

    But note: This simplification holds only if S is a forest (acyclic, max degree ≤2? Actually for any forest, edges = vertices - components. So it's true if S has no cycles. But we also need max degree ≤2? Actually if S has a vertex with degree 3, it could still be a forest? A tree can have a vertex of degree 3, but in our context, can a permutation contain three required edges incident to the same vertex? Let's see: Suppose S has edges {1,2}, {1,3}, {1,4}. That's a star with center 1 degree 3. Is it possible for a permutation to contain all three edges? That would require vertex 1 to be adjacent to 2,3,4 in the permutation. But in a linear ordering, a vertex can have at most two neighbors. So it's impossible. So S with a vertex degree >2 leads to f(S)=0, regardless of being acyclic. So for f(S) to be non-zero, S must be a forest with maximum degree ≤2, i.e., a linear forest. In that case, it's true that |V_S| - c = |S|. So we can compute G = N - |S|.

    Let's double-check: For a linear forest (disjoint union of paths), each component is a path; if a component has L_i edges and V_i = L_i+1 vertices, then sum L_i = |S|, sum V_i = |V_S|, and c = number of components. Then |V_S| = |S| + c, so indeed |V_S| - c = |S|. So G = c + (N - |V_S|) = N - (|V_S| - c) = N - |S|. So it's consistent. So we can compute f(S) = fact[N - |S|] * (2^c) mod MOD, provided S is a linear forest. This is even simpler: we only need to know |S| and c (number of components). And also need to check that S is a linear forest (max degree ≤2 and acyclic). So we don't need to compute |V_S| explicitly.

    But caution: In case of a component that is an isolated vertex (impossible). So fine.

    Thus compute_f can be optimized:

    • If any vertex degree >2 -> return 0.
    • Then check for cycles and compute number of components c (by traversing). Actually we can compute c during traversal, and also detect cycles. If during traversal we find a component with all vertices degree 2 (i.e., no vertex degree 1), then it's a cycle => return 0.
    • If passes, then f = fact[N - len(edges_subset)] * (1 << c) % MOD.

    This is simpler, as we don't need to compute |V_S| explicitly. However, we need to be sure that |V_S| - c = |S| automatically holds when degrees ≤2 and no cycles? Actually the relation |V_S| = |S| + c holds for any forest (acyclic graph). If the graph is acyclic, it's a forest, so each component is a tree. For a tree, V_i = E_i + 1. Summing: total V = total E + c, so V = |S| + c. So this holds regardless of degree constraints, as long as the graph is acyclic. So if we have an acyclic graph with max degree ≤2, it's a forest of paths, but even if it had a vertex degree 3 but acyclic, it could be a tree with branching, but such a tree would not satisfy max degree ≤2, which we already rejected. So for our valid sets, indeed the forest condition is implied by acyclicity and degree ≤2 (though degree ≤2 enforces each component is a path). So we can rely on acyclicity to guarantee V = |S| + c. But we also need to ensure no cycles. So if we check for cycles and also ensure degrees ≤2, then V = |S| + c automatically. However, when we compute c by counting components in the graph, we need V. But we might not need V if we compute G as N - |S|. Let's verify: G = c + (N - V) = N - (V - c) = N - |S| (since V - c = |S| if acyclic). So if we have passed cycle check, we can compute f as fact[N - |S|] * 2^c. But we must be careful: The cycle check may return false if there is a cycle; but we also must ensure that degrees ≤2. Suppose we have a component that is a cycle; then it is not acyclic, but we will detect it via the "has_degree1" check (since all degrees 2). We'll return 0. So for cases we don't return 0, we have an acyclic graph with max degree ≤2. So V - c = |S| holds. Good.

    Thus compute_f can be:

    def compute_f(N, edges): if not edges: return fact[N] deg = {} adj = {} for u,v in edges: deg[u] = deg.get(u,0)+1 deg[v] = deg.get(v,0)+1 adj.setdefault(u,[]).append(v) adj.setdefault(v,[]).append(u) for d in deg.values(): if d > 2: return 0 visited = set() components = 0 for v in deg: if v in visited: continue # traverse stack = [v] visited.add(v) has_degree1 = False while stack: x = stack.pop() if deg[x] == 1: has_degree1 = True for nb in adj[x]: if nb not in visited: visited.add(nb) stack.append(nb) if not has_degree1: return 0 components += 1 # Valid forest G = N - len(edges) # because |S| = len(edges) f = fact[G] * (1 << components) % MOD return f

    But careful: Is it always true that G = N - |S|? Let's test with examples: For empty set, |S|=0, G=N, fact[N] correct. For single edge: |S|=1, G = N-1, f = fact[N-1] * 2. That matches earlier. For two disjoint edges: |S|=2, G = N-2, f = fact[N-2] * 2^2 = fact[N-2] * 4. Good. For path of two edges: |S|=2, G = N-2, f = fact[N-2] * 2^1 = fact[N-2] * 2. That matches earlier computed f= (N-2)! * 2. Good. So yes.

    Now, we should double-check for case where S contains an edge that is a self-loop? Not possible.

    Thus we can use this simplified formula.

    Now, we need to compute c (number of components). In case of valid forest, c = |V| - |S|. But we compute c directly by traversal. That's fine.

    Now, one more check: Could there be a scenario where the graph has a component that is a tree but has a vertex of degree 2? That's a path; we count it as one component. Good.

    Now, what about a component that is a single edge? That's also a tree with two vertices each degree 1, so it has a degree-1 vertex. So has_degree1 true. So valid.

    Now, about cycle detection: In a component where all vertices have degree 2, it's a cycle. But also consider a component that is a single vertex? Not possible. So detection works.

    But what if the graph has a component that is two vertices connected by two parallel edges? Not possible since S is set of distinct edges.

    Thus fine.

    Now, we can proceed.

    But we need to be careful: The graph built from S may have multiple edges? No.

    Now, we also need to consider that some missing edges could be repeated? We dedup.

    Now, about the size of factorial array: N up to 1e5, so fact up to 100000 is enough. But what about G = N - |S|, which can be as low as N-7, so still within range.

    Now, we should ensure that for each test case, we compute ans modulo MOD correctly. Use modulo addition and subtraction.

    Now, let's think about potential pitfalls: In counting f(S), we used the grouping argument. However, is there any case where S forms a forest but the required edges force certain blocks to have orientations that are not independent? For example, consider S containing two edges that are not in same component but share a vertex? That would be same component. So independent across components. So orientation independent.

    Now, consider S containing edges that form a path, but could the orientation of that path affect the count of permutations where the path appears? No, because we count all permutations that contain those edges. For each permutation, the orientation is determined. Our counting of 2 orientations per component accounts for both possibilities. So it's fine.

    Now, verify with a more complex valid set: S = path of length 3 (3 edges) on vertices a,b,c,d. Then |S|=3, c=1, G = N-3. f = fact[N-3] * 2. Let's test with N=4: then G=1, f = 1! * 2 =2, which matches earlier for N=4 path of 3 edges gave 2 permutations. Good.

    Now, with N=5, S = path of 3 edges on vertices 1,2,3,4, and also an isolated edge {5,6}? But N=5 cannot have vertex 6. So consistent.

    Now, edge case: S may contain edges that are not incident to some vertices, leaving many free vertices.

    Thus algorithm is ready.

    Now, let's consider whether we need to handle large N for factorial precomputation. We'll precompute up to maximum N across test cases. To do that, we can read all test cases first, or just precompute up to 100000. Since N ≤ 1e5, we can precompute up to 100000 globally.

    Now, final step: implement solve().

    Pseudo:

    import sys sys.setrecursionlimit(1<<25) MOD = 10**9+7 MAXN = 100000

    fact = [1]*(MAXN+1) for i in range(1,MAXN+1): fact[i] = fact[i-1]*i % MOD

    def compute_f(N, edges): if not edges: return fact[N] deg = {} adj = {} for (u,v) in edges: deg[u] = deg.get(u,0)+1 deg[v] = deg.get(v,0)+1 adj.setdefault(u,[]).append(v) adj.setdefault(v,[]).append(u) for d in deg.values(): if d > 2: return 0 visited = set() components = 0 for v in deg: if v in visited: continue # DFS stack = [v] visited.add(v) has_degree1 = False while stack: x = stack.pop() if deg[x] == 1: has_degree1 = True for nb in adj[x]: if nb not in visited: visited.add(nb) stack.append(nb) if not has_degree1: # all degree 2 -> cycle return 0 components += 1 G = N - len(edges) return fact[G] * (1 << components) % MOD

    def solve(): import sys data = sys.stdin.read().strip().split() if not data: return it = iter(data) T = int(next(it)) out_lines = [] for _ in range(T): N = int(next(it)) M = int(next(it)) missing_set = set() for i in range(M): u = int(next(it)); v = int(next(it)) if u > v: u,v = v,u missing_set.add((u,v)) missing = list(missing_set) M = len(missing) ans = 0 for mask in range(1<<M): edges_subset = [missing[i] for i in range(M) if (mask>>i)&1] f = compute_f(N, edges_subset) if bin(mask).count('1') % 2 == 1: ans = (ans - f) % MOD else: ans = (ans + f) % MOD out_lines.append(str(ans)) sys.stdout.write("\n".join(out_lines))

    if name == "main": solve()

    Now, we should test with given example.

    Let's simulate quickly:

    T=2 Test1: N=4, M=3 edges: (1,2),(2,3),(3,4). No duplicates. Compute subsets:

    Empty: f=24, ans=24 mask1 (1<<0): edges [(1,2)] f=12, ans=24-12=12 mask2: [(2,3)] f=12, ans=12-12=0 mask3: both (1,2) and (2,3) -> edges_subset length 2, check validity: deg: 1:1,2:2,3:1 -> max deg 2 ok. Graph: component 1-2-3, has_degree1? vertices 1 and 3 degree1, so has_degree1 True. components=1. f= fact[4-2]=fact[2]=2 * (1<<1)=2 => f=4. mask size=2 even so add: ans=0+4=4. mask4: [(3,4)] f=12, ans=4-12=-8 mod => -8 mod 1e9+7 = huge but we keep mod: (4-12)%MOD = (MOD+4-12) = MOD-8? Actually we'll do (ans - f) % MOD, which yields positive. So ans becomes MOD-8? but later we add others so final 2. So proceed. mask5: (1,2),(3,4): edges disjoint: deg 1:1,2:1,3:1,4:1; components: two components (each edge) -> c=2; f= fact[4-2]=2! =2, times 2^2=4 => f=8. mask size=2 even -> ans = (previous) +8? But previous ans after mask4 is (4-12) mod = MOD-8? Actually let's recalc sequentially with mod:

    Initialize ans=0

    mask0: +24 -> ans=24 mask1: -12 -> ans=12 mask2: -12 -> ans=0 mask3: +4 -> ans=4 mask4: -12 -> ans = (4-12)%MOD = (MOD+4-12) = MOD-8 = 1000000007-8 = 999999999? Actually that's a large number. But we should continue. mask5: +8 -> ans = ( (MOD-8) + 8 ) % MOD = MOD = 0? Actually (MOD-8+8)=MOD -> MOD % MOD = 0. mask6: (2,3),(3,4): similar to mask3? edges (2,3),(3,4): path 2-3-4, f=4. mask size=2 even -> ans = 0+4=4. mask7: all three edges: (1,2),(2,3),(3,4): length 3, graph is path 1-2-3-4, c=1, f= fact[4-3]=1! *2=2. mask size=3 odd -> ans = 4 - 2 = 2.

    So final ans=2. Good.

    Second test: N=2, M=1 edge (1,2). Missing = [(1,2)]. mask0: f=2! =2 -> ans=2 mask1: f = fact[2-1]=1! *2 =2 -> mask odd: ans=2-2=0. Output 0. Good.

    Thus works.

    Now, potential issues:

    • The graph for S may have components that are isolated? Not.

    • When we compute components, we need to ensure we traverse all vertices in deg. That's fine.

    • For the cycle detection: The condition "not has_degree1" indicates all vertices in component have degree 2. For a component with one vertex and a self-loop? Not possible. For component with two vertices each degree 2 would require two parallel edges, not possible. So that works.

    • But what about a component that is a single edge where both vertices have degree 1? has_degree1 True, so not cycle.

    • Also, if graph has a component that is a path but all vertices have degree 2? That would be a cycle, not a path. So fine.

    Now, there is nuance: A component could be a single vertex with degree 0? Not in V_S. So ignore.

    Now, we must also consider that the graph of S could have a vertex with degree 0? Not possible because we only include vertices that appear in edges.

    Thus all good.

    Now, time to think about any hidden constraints: M ≤ 7, but N up to 1e5, T up to 10, so total operations ~10128some = negligible.

    Now, memory: factorial array of size 100001, fine.

    Now, note that the modulo exponentiation for 2^c is trivial.

    Now, edge case: When N - |S| may be negative? Since |S| ≤ 7 and N ≥ 1, but could N be less than |S|? For example, N=2, |S| could be 2? But M is number of missing edges, M ≤ 7, but missing edges are pairs of vertices from 1..N. If N=2, the maximum number of distinct missing edges is 1 (only pair (1,2)). So |S| cannot exceed number of possible distinct pairs, which is at most C(N,2). So if N is small, M could be up to C(N,2). But constraint M ≤ 7 and N can be as low as 1. So it's possible that M > C(N,2)? Actually input could give M pairs, but they must be pairs of vertices between 1 and N. If N=2, only possible pair is (1,2). So M can be at most 1, but the problem statement doesn't guarantee that M ≤ C(N,2). It says 0 ≤ M ≤ 7, and M lines follow each containing a pair of indices of vertices. It's possible that they give M=2 with pairs (1,2) and (1,2) duplicate? But duplicates may occur. But after dedup, the actual number of distinct missing edges may be ≤ C(N,2). So |S| ≤ min(M, C(N,2)). In subset enumeration, we only consider distinct edges. So if N=2 and distinct missing edges=1, then |S| ≤1, so N - |S| >=1. So no negative. For N=1, C(1,2)=0, so M must be 0 (since no pair exists). So safe.

    Thus factorial index G will be non-negative.

    Now, final check: The algorithm uses a global factorial array sized MAXN. But if N can be up to 1e5, we need MAXN = 100000. However, could N be 100000 exactly? Then we need fact[100000]. That's fine.

    Now, note that we might need factorial up to N, but G = N - |S| ≤ N, so fine.

    Now, we might also consider precomputing powers of 2 up to 7.

    Now, implement in Python. Should be fast.

    Now, let's think about potential improvements: none needed.

    Now, finalize solution.

    Before final answer, we should consider a more complex scenario: what if missing edges set contains an edge multiple times? We dedup. That's important because inclusion-exclusion over duplicates would be wrong. So we dedup.

    Now, note: The problem statement says "M lines follow, each containing a pair of indices of vertices, indicating that those vertices are not connected by an edge." It does not guarantee that the pairs are distinct. To be safe, we dedup.

    Now, what about the order of vertices in pair? We treat unordered.

    Now, everything is set.

    Now, we can produce final solution explanation.

    But wait: There might be a nuance: In the definition of connected permutation, they say "there is an edge between vertices p[i] and p[i+1] for all natural numbers i less than N". That means the graph must contain an edge for each consecutive pair. If the graph has no edge (i.e., missing), then permutation not connected. That's what we used.

    Now, we must ensure that the graph is undirected, so the adjacency condition is symmetric. Our inclusion-exclusion over missing edges (unordered) and counting permutations with forced adjacency (unordered) is correct.

    Now, I'm thinking about potential oversight: The inclusion-exclusion principle we used is standard for counting permutations that avoid a set of forbidden adjacencies. However, we must be careful: The events A_i (edge i appears as consecutive) are not independent, but inclusion-exclusion works. However, in the standard formula, the number of permutations that avoid all forbidden adjacencies is indeed sum_{S ⊆ F} (-1)^{|S|} * N(S), where N(S) is number of permutations where all edges in S are present as adjacencies. That's correct.

    Now, is there any overcount/undercount due to permutations that contain a particular edge more than once? As argued, not possible.

    Thus final solution.

    Now, let's test with some random small values using mental or quick reasoning:

    N=3, missing edges: (1,2) only. Then answer should be total permutations minus those where 1 and 2 are adjacent. total=6, f({1,2})=4 (as earlier). So ans=2. Which permutations are valid? Those where 1 and 2 are not adjacent. Permutations of 3: list all: 123 (1-2 adjacent) invalid; 132 (1-3,3-2) 1 and2 not adjacent? They are not consecutive, so valid; 213 (2-1 adjacent) invalid; 231 (2-3,3-1) 1 and2 not adjacent? They are not consecutive; 312 (3-1,1-2) 1-2 adjacent? Actually 312: pairs (3,1) and (1,2): 1 and 2 adjacent, invalid; 321 (3,2,1): 2-1 adjacent invalid. So valid: 132 and 231 -> 2. Good.

    Now test N=3, missing edges: (1,2) and (2,3). We computed ans=0? Actually earlier we computed for N=3, missing edges both (1,2) and (2,3). Our inclusion-exclusion: total 6, f({1,2})=4, f({2,3})=4, f({1,2},{2,3})=2, ans=6-4-4+2=0. So no valid permutations. Check manually: need to avoid adjacency of 1-2 and 2-3. All permutations: 123 (has both 1-2 and 2-3) invalid; 132 (1-3,3-2) has 2-3? Actually 3-2 is adjacent, so forbidden (2,3) appears? 3-2 is adjacency of 2 and3, so invalid; 213 (2-1,1-3) has 1-2 adjacency (2-1) invalid; 231 (2-3,3-1) has 2-3 adjacency invalid; 312 (3-1,1-2) has 1-2 adjacency invalid; 321 (3-2,2-1) has both 2-3 and 1-2? Actually 3-2 gives 2-3 adjacency, invalid. So indeed none valid. So ans=0.

    Works.

    Now, test N=4, missing edges: (1,2) and (3,4). We computed ans = total 24 - 12 -12 +8 = 8. So answer 8. Let's list manually: permutations where 1 and 2 not adjacent and 3 and 4 not adjacent. Could count? Possibly 8. Seems plausible.

    Thus algorithm appears consistent.

    Now, we should also verify the scenario where missing edges set includes edges that form a cycle of length 3 as earlier, which gave answer 0. Works.

    Now, consider case N=5, missing edges: (1,2), (2,3), (3,4), (4,5). That's a path of 4 edges. Our inclusion-exclusion will involve many subsets, but final answer should be computed. We can test small with program later.

    Thus final answer ready.

    Now, let's produce the final explanation for solution.

    But before finalizing, let's consider whether there is any alternative approach or trick we might have missed. However, given constraints M ≤ 7, inclusion-exclusion is the intended solution.

    Now, potential pitfalls: We must be careful that the graph built for S may have vertices that are not necessarily in 1..N? They are, as edges come from missing set, so vertices are within 1..N.

    Now, memory for adjacency: we use dict of lists, fine.

    Now, note that for each subset we rebuild deg and adj; this is okay.

    Now, about Python speed: 10*128 * (up to 14 operations) = trivial.

    Now, final code.

    But wait: There is a nuance: In inclusion-exclusion, we are counting permutations that avoid all missing edges as adjacency. However, is it possible that a permutation contains a missing edge but still counted because we subtract? That's handled.

    Now, is there any condition about the graph being undirected? The edges are undirected, so adjacency condition is symmetric.

    Now, final answer.

    Now, we should produce the solution.

    But the problem might be from some contest and might have intended solution using inclusion-exclusion as we did. So it's fine.

    Now, I will write a final answer with explanation and code.

    But before final output, we should also think about whether we need to handle N=0? No, N≥1.

    Now, finalize.

    Now, produce final response. ```python import sys

    MOD = 10**9 + 7 MAXN = 100000

    precompute factorials modulo MOD

    fact = [1] * (MAXN + 1) for i in range(1, MAXN + 1): fact[i] = fact[i - 1] * i % MOD

    def count_containing_permutations(N, edges): """ Count permutations of N distinct vertices that contain every unordered pair in 'edges' as a consecutive pair (in either order). 'edges' is a list of tuples (u, v) with u < v. Returns 0 if it is impossible (max degree > 2 or a cycle appears). """ if not edges: return fact[N]

    deg = {}
    adj = {}
    for u, v in edges:
        deg[u] = deg.get(u, 0) + 1
        deg[v] = deg.get(v, 0) + 1
        adj.setdefault(u, []).append(v)
        adj.setdefault(v, []).append(u)
    
    # degree > 2 makes adjacency impossible in a linear path
    for d in deg.values():
        if d > 2:
            return 0
    
    visited = set()
    components = 0
    
    for v in deg.keys():
        if v in visited:
            continue
        # DFS to explore one connected component
        stack = [v]
        visited.add(v)
        has_degree_one = False
        while stack:
            x = stack.pop()
            if deg[x] == 1:
                has_degree_one = True
            for nb in adj[x]:
                if nb not in visited:
                    visited.add(nb)
                    stack.append(nb)
        # If no vertex of degree 1, the component is a cycle (all degrees = 2)
        if not has_degree_one:
            return 0
        components += 1
    
    # For a forest (acyclic) we have |V| = |edges| + components,
    # so the number of groups = components + (N - |V|) = N - |edges|
    groups = N - len(edges)
    return fact[groups] * (1 << components) % MOD
    

    def solve() -> None: data = sys.stdin.read().strip().split() if not data: return it = iter(data) t = int(next(it)) out = [] for _ in range(t): N = int(next(it)) M = int(next(it)) # read edges, normalize to (min,max) and remove duplicates missing_set = set() for _ in range(M): u = int(next(it)) v = int(next(it)) if u > v: u, v = v, u missing_set.add((u, v)) missing = list(missing_set) # distinct edges m = len(missing)

        ans = 0
        for mask in range(1 << m):
            subset = [missing[i] for i in range(m) if (mask >> i) & 1]
            cnt = count_containing_permutations(N, subset)
            if bin(mask).count('1') & 1:
                ans = (ans - cnt) % MOD
            else:
                ans = (ans + cnt) % MOD
        out.append(str(ans))
    
    sys.stdout.write("\n".join(out))
    

    if name == "main": solve()