“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图1所示。


图1 六度空间示意图
“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入格式:

输入第1行给出两个正整数，分别表示社交网络图的结点数NN（1<N\le 10^41<N≤10
4
 ，表示人数）、边数MM（\le 33\times N≤33×N，表示社交关系数）。随后的MM行对应MM条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到NN编号）。

输出格式:

对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。

输入样例:

10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
输出样例:

1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%

#include <stdio.h>
#include <stdlib.h>
int N,M ; //节点数，边数
int graph[10001][10001] ; //顶点从1开始编号
int count  ;
int visited[10001] ;

typedef struct quedeNode
{
    int rear ;
    int front ;
    int data[ 10000 ] ;
} quede ;

void initQ( quede* Q )
{
    Q->rear = 0  ;
    Q->front = 0 ;
}


void addQ( quede* Q , int item)
{
    Q->data[ Q->rear ] = item ;
    Q->rear++ ;
}


int  deleteQ( quede* Q  )
{
    int i ;
    i = Q->front ;
    Q->front++   ;
    return Q->data[ i ] ;
}


int isEmptyQ( quede* Q )
{
    if( Q->front == Q->rear )
        return 1 ;
    else return 0 ;
}


void BFS( int curV, quede* Q )
{
    int last , tail ;
    int i,v ;
    int level = 0 ;

    addQ( Q , curV ) ;
    last = curV ;
    visited[ curV ] = 1 ;
    while( !isEmptyQ( Q ) )
    {
        v = deleteQ( Q ) ;    
        
        for(i=1; i<=N; i++)
        {
            if( graph[v][i]==1 && visited[i]==0 )//有边连接且未被访问
            {    
                tail = i ;//保存最后一个入队的结点
                count++ ;        
                addQ( Q , i ) ;
                visited[ i ] = 1 ;     //入队顶点标记    
            }
        }

        //考虑换个位置
        if( v==last )//上一层最后一个入队的顶点出队则层数加1
        {
            last = tail ;
            level++ ;    //层数加1
        }

        if( level==6 ) break ;
    }
}


void six( )
{
    int i,j ;
    double percent ;
    quede* Q ;

    Q = (quede*)malloc( sizeof( quede ) ) ;

    
    for( i=1; i<=N; i++ )
    {    
        for( j=1; j<=N; j++ )
            visited[ j ] = 0 ;
        initQ( Q );
        count = 1 ;
        BFS( i , Q ) ;
        
        percent = (double)count/N ;//count转换为浮点数计算除法
        printf( "%d: %.2f%%\n",i,percent*100 ) ;
    }
    
}






int main(   )
{
    int i,j ;
    int v1,v2 ;

    scanf("%d%d",&N,&M);

    for(i=1; i<=N; i++)
        for(j=1; j<=N; j++)
            graph[i][j] = 0 ;



    for( i=1 ; i<=M; i++ )
    {
        scanf("%d%d" , &v1,&v2);
        graph[v1][v2] = graph[v2][v1] = 1 ;
    }

    six( ) ;
    return 0 ;
}