JOIN

 Problem Statement

Problem Statement for Fragile

Problem Statement

You are given two ints: N and K. Lun the dog is interested in the undirected graphs that satisfy the following conditions:

• The graph has exactly N vertices, labeled from 0 to N-1. Each vertex has a unique label.
• The graph has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices.
• The graph has exactly K bridges (edges whose deletion increases its number of connected components).

Find and return the number of these graphs modulo 1,000,000,007.

Definition

 Class: Fragile Method: countGraphs Parameters: int, int Returns: int Method signature: int countGraphs(int N, int K) (be sure your method is public)

Notes

-Two graphs are considered different if and only if there exists a pair of vertices such that one of the graphs contains an edge between them, and the other does not.

Constraints

-N will be between 1 and 50, inclusive.
-K will be between 0 and N-1, inclusive.

Examples

0)

 `3` `2`
`Returns: 3`
 The following three graphs satisfy the conditions:
1)

 `4` `0`
`Returns: 15`
 The following 15 graphs satisfy the conditions:
2)

 `5` `2`
`Returns: 195`
 The following is some of the graphs that satisfy the conditions: Here, bridges are painted in brown, and "x n" represents that there are n graphs that are isomorphic to that graph.
3)

 `50` `25`
`Returns: 353637389`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
Single Round Match 648 Round 1 - Division I, Level Three