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,那么就是生成树中,白边的最大数量),再求一遍最小生成树(最小白边数量),判断中间是否有斐波那契数即可.原理:对于一个带权图来说,我们考虑如果只有n-1条边,那么最大生成树和最小生成树是一样的,而只要出现>n-1条边,便会出现环,这就使得,链接两个点之间可能有多条路,为什么最小生成树和最大生成树不同?因为两个点之间都选择了最大权值链接(最大生成树),而最小生成树则不然,所以,任何权值的生成树都可以在这两个(max与min)之间选择,还不明白,考虑极端情况,如果最小生成树,凡是有两个点之间有多条路的,都选择最大权值相连这两个点,就成了最大生成树,所以中间的生成树可以通过选择部分改变来生成

代码:

//#include<bits/stdc++.h>
#define ll long long
#include <stdio.h>
#include <algorithm>
#pragma GCC optimize(2)
using namespace std;
const int maxn=1e6+1000;
const int INF=1e9+7;
inline ll read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll n,m;
struct node{
    int s,e;
    int f;
}edge[maxn];
int pre[maxn];
int save[1000];
int Find(int x)
{
    return pre[x]==x?x:pre[x]=Find(pre[x]);
}
bool Merge(int x,int y)
{
    int fx=Find(x);
    int fy=Find(y);
    if(fx!=fy)
    {
        pre[fy]=fx;
        return true;
    }
    return false;
}
bool cmp1(node a,node b)
{
    return a.f>b.f;
}
bool cmp2(node a,node b)
{
    return a.f<b.f;
}
int main()
{
    int cnt=0;
    save[++cnt]=1;save[++cnt]=2;
    for(int i=3;i;i++)
    {
        save[++cnt]=save[i-1]+save[i-2]; 
        if(save[i-1]+save[i-2]>100100) break;
    }
    int T;scanf("%d",&T);
    int cas=0;
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].f);
        for(int i=1;i<=n+1;i++) pre[i]=i;
        sort(edge+1,edge+1+m,cmp1);//decreasing
        int ans=0,res=0,res1=0;
        for(int i=1;i<=m&&ans<n-1;i++)
        {
            if(Merge(edge[i].s,edge[i].e))
            {
                ans++;
                res+=edge[i].f;
            }
        }
        if(ans!=n-1)
        {
            printf("Case #%d: No\n",++cas);
            continue;
        }
        for(int i=1;i<=n+1;i++) pre[i]=i;
        sort(edge+1,edge+1+m,cmp2);
        ans=0;
        for(int i=1;i<=m&&ans<n-1;i++)
        {
            if(Merge(edge[i].s,edge[i].e))
            {
                ans++;
                res1+=edge[i].f;
            }
        }
        bool flag=false;
        for(int i=1;i<=cnt;i++)
        {
            if(save[i]>res) break;
            if(save[i]>=res1&&save[i]<=res)
            {
                flag=true;
                break;
            }
        }
        if(flag) printf("Case #%d: Yes\n",++cas);
        else printf("Case #%d: No\n",++cas);
    }
    return 0;
}