Description

　　Coach Pang is interested in Fibonacci numbers while Uncle Yang wants him to do some research on Spanning Tree. So Coach Pang decides to solve the following problem:
　　Consider a bidirectional graph G with N vertices and M edges. All edges are painted into either white or black. Can we find a Spanning Tree with some positive Fibonacci number of white edges?
(Fibonacci number is defined as 1, 2, 3, 5, 8, ... )
 

Input

　　The first line of the input contains an integer T, the number of test cases.
　　For each test case, the first line contains two integers N(1 <= N <= 10 5) and M(0 <= M <= 10 5).
　　Then M lines follow, each contains three integers u, v (1 <= u,v <= N, u<> v) and c (0 <= c <= 1), indicating an edge between u and v with a color c (1 for white and 0 for black).
 

Output

　　For each test case, output a line “Case #x: s”. x is the case number and s is either “Yes” or “No” (without quotes) representing the answer to the problem.
 

Sample Input

2 4 4 1 2 1 2 3 1 3 4 1 1 4 0 5 6 1 2 1 1 3 1 1 4 1 1 5 1 3 5 1 4 2 1
 

Sample Output

Case #1: Yes Case #2: No
 

给定无向图每个边要么是白色，要么是黑色。求生成树的白边个数能否是斐波那契数。其实应该能想到的，让白边是1，黑边是0，求最大生成树和最小生成树。看中间范围是否有斐波那契数。注意是无向图，加边加两个！kruskal返回-1就是不连通呀，没必要拿并查集来判断~

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
const int maxm=200005;
int F[maxn];
struct Edge
{
    int u,v,w;
}edge[maxm];
int tol;
void addedge(int u,int v,int w)
{
    edge[tol].v=v;
    edge[tol].u=u;
    edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
bool cmp2(Edge a,Edge b)
{
    return a.w>b.w;
}
int fnd(int x)
{
    return x==F[x]?x:F[x]=fnd(F[x]);
}
int kruskal(int n)
{
    for(int i=1;i<=n;i++) F[i]=i;
   // sort(edge,edge+tol,cmp);
    int cnt=0;
    int ans=0;
    for(int i=0;i<tol;i++)
    {
        int u=edge[i].u;
        int v=edge[i].v;
        int w=edge[i].w;
        int a=fnd(u);
        int b=fnd(v);
        if(a!=b)
        {
            ans+=w;
            F[b]=a;
            cnt++;
        }
        if(cnt==n-1)break;
    }
    if(cnt<n-1)return -1;
    return ans;
}
int num[100],cnt;
void init()
{
    num[0]=0;num[1]=1;num[2]=2;num[3]=3;
    cnt=4;
    while(num[cnt-1]<=100005)
    {
        num[cnt]=num[cnt-1]+num[cnt-2];
        cnt++;
       // cout<<num[cnt-1]<<endl;
    }
}
int main()
{
    //freopen("cin.txt","r",stdin);
    int t,n,m,cas=1;
    scanf("%d",&t);
    init();
    while(t--)
    {
        scanf("%d%d",&n,&m);
        tol=0;
        while(m--)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);///!!!
        }
        printf("Case #%d: ",cas++);
        sort(edge,edge+tol,cmp);
        int small=kruskal(n);
        bool ff=true;
        sort(edge,edge+tol,cmp2);
        int big=kruskal(n);
       // printf("s=%d,b=%d\n",small,big);
        if(small==-1||big==-1)
        {
            puts("No");
            continue;
        }
        bool flag=false;
        for(int i=1;i<=23;i++)
        {
            if(num[i]>=small&&num[i]<=big)
            {
                flag=true;
                break;
            }
        }
        if(flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}