1750: FractalWheels

An undirected graph is said to be a wheel if there exists a "center" vertex which is adjacent to all other vertices in the graph, and the subgraph induced by taking all other vertices of the graph is precisely a cycle. Additionally, any wheel must have at least 3 vertices in the cycle surrounding the center vertex. The span of a wheel is the degree of the center vertex. For example, the graph below is a wheel with span 4 (the center vertex is colored black). We define a fractal wheel with depth d and span h as follows: a fractal wheel with depth 0 and span h is simply a wheel with span h. To obtain a fractal wheel with depth d > 0 and span h, we first take a fractal wheel with depth d-1 and span h. Let V be the set of all vertices at distance d from the center vertex of this fractal wheel. For each vertex u in V, add to the graph a new wheel with span h such that its center vertex is u. Each added wheel must be vertex-disjoint from the other added wheels. The resulting graph is a fractal wheel with depth d and span h, and the center vertex of the resulting fractal wheel is the same as the center vertex of the initial fractal wheel with depth d-1. For example, the graph below is a fractal wheel with depth 1 and span 4 (note that adding or removing any edges from this graph would result in a graph which is not a fractal wheel): Given a graph G with N vertices numbered 0 to N-1, inclusive, you must determine if G is a fractal wheel. Notes: - The distance between two vertices in a graph is the length of the shortest path between them (or infinity if there is no path). - The degree of a vertex v in a graph G is the total number of vertices in G which are adjacent to v.

There are several test cases, each test cases have two parts.Part one will give two integers N and P.N is the number of the number of the vertexs,and the P is the number of the edges.The second line contains P pairs of integers ,each pairs contains two integers U and V,which denote that there is an edge between U and V. 2<=N<=1000 , 1<=P<=500

Two integers the depth D and span H.If G is not a fractal wheel,output two zeros.

5 8
0 1 0 2 0 3 0 4 1 2 2 3 3 4 1 4 
21 40
0 1 0 2 0 3 0 4 1 2 1 4 1 5 1 6 1 7 1 8 2 3 2 9 2 10 2 11 2 12 3 4 3 13 3 14 3 15 3 16 4 17 4 18 4 19 4 20 5 6 5 8 6 7 7 8 9 10 9 12 10 11 11 12 13 14 13 16 14 15 15 16 17 18 17 20 18 19 19 20
13 25
0 1 0 2 0 3 1 2 1 3 1 4 1 5 1 6 2 3 2 7 2 8 2 9 3 10 3 11 3 12 4 5 4 6 5 6 7 8 7 9 8 9 10 11 10 12 11 12 0 7

0 4
1 4
0 0