C. Stickmen

Codeforces

IDCF10113C

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Limak is a little bear who loves to play with graphs. Recently, he defined a new structure in a graph and called it a _stickman_. A stickman is a set of 7 different vertices and 6 edges. Vertices should be connected by edges as in the image below. You can see here two legs, two arms and a head. Formally, one vertex (the one between arms) must be connected to four other vertices and one of these four must be connected to two more vertices. Limak has an undirected graph with n vertices and m edges, without loops and multiple edges. He asks you a favor. Could you count how many stickmen there are in Limak's graph, modulo 109 + 7? A stickman is defined by a set of 7 vertices and 6 edges. Two stickmen are different if and only if the set of vertices isn't the same or the set of edges isn't the same. The order of vertices or edges doesn't matter (so you shouldn't distinguish legs for example). The first line of the input contains two integers n and m (7 ≤ n ≤ 200, ) — the number of vertices and the number of edges. Vertices are numbered 1 through n. Each of the next m lines contains two integers ai and bi (1 ≤ ai, bi, ai ≠ bi) — indices of two vertices connected with an edge. Any unordered pair of vertices will appear at most once. Print the number of stickmen in the given graph, modulo 109 + 7. There are two different stickmen in the sample, showed in the drawing below. Since there are only 7 vertices in the graph, the set of vertices of each stickman must contain all vertices. The two stickmen don't have the same set of edges though and this is why they are different at all. ## Input The first line of the input contains two integers n and m (7 ≤ n ≤ 200, ) — the number of vertices and the number of edges. Vertices are numbered 1 through n.Each of the next m lines contains two integers ai and bi (1 ≤ ai, bi, ai ≠ bi) — indices of two vertices connected with an edge. Any unordered pair of vertices will appear at most once. ## Output Print the number of stickmen in the given graph, modulo 109 + 7. [samples] ## Note There are two different stickmen in the sample, showed in the drawing below. Since there are only 7 vertices in the graph, the set of vertices of each stickman must contain all vertices. The two stickmen don't have the same set of edges though and this is why they are different at all.

**Definitions** Let $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $. A *stickman* is a subgraph $ H \subseteq G $ with exactly 7 vertices and 6 edges, such that: - There exists a central vertex $ c \in V(H) $ of degree 4 in $ H $. - Among the 4 neighbors of $ c $, exactly one (call it $ h $) has degree 2 in $ H $; the other three have degree 1 in $ H $. - The vertex $ h $ is connected to exactly one additional vertex $ d \in V(H) \setminus \{c\} $, which has degree 1 in $ H $. - All other vertices in $ H $ (besides $ c $, $ h $, and $ d $) have degree 1. Thus, the degree sequence of $ H $ is: one vertex of degree 4, one vertex of degree 2, and five vertices of degree 1. **Constraints** 1. $ 7 \leq n \leq 200 $ 2. $ m \geq 6 $ 3. $ G $ has no loops or multiple edges. **Objective** Count the number of distinct stickman subgraphs in $ G $, modulo $ 10^9 + 7 $. A stickman is uniquely determined by its set of 7 vertices and 6 edges (unordered). Let $ \mathcal{S} $ be the set of all stickman subgraphs of $ G $. Compute $ |\mathcal{S}| \mod (10^9 + 7) $.

API Response (JSON)

{
  "problem": {
    "name": "C. Stickmen",
    "description": {
      "content": "Limak is a little bear who loves to play with graphs. Recently, he defined a new structure in a graph and called it a _stickman_. A stickman is a set of 7 different vertices and 6 edges. Vertices sho",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10113C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Limak is a little bear who loves to play with graphs. Recently, he defined a new structure in a graph and called it a _stickman_.\n\nA stickman is a set of 7 different vertices and 6 edges. Vertices sho...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $.  \nA *stickman* is a subgraph $ H \\subseteq G $ with exactly 7 vertices and 6 edges, such that:  \n- There exis...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments