Problem 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⁵) and M(0 <= M <= 10⁵).
　　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

 

Sample Output

 

Source

 

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013-11-16 14:14:50

 File Name     :E:\2013ACM\专题强化训练\区域赛\2013成都\1006.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 int f[];

 struct Edge

 {

     int u,v,c;

 }edge[];

 int F[];

 int find(int x)

 {

     if(F[x] == -)return x;

     return F[x] = find(F[x]);

 }

 bool cmp1(Edge a,Edge b)

 {

     return a.c < b.c;

 }

 bool cmp2(Edge a,Edge b)

 {

     return a.c > b.c;

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int tot = ;

     f[] = ;

     f[] = ;

     while(f[tot] <= )

     {

         f[tot+] = f[tot] + f[tot-];

         tot++;

     }

     int T;

     int iCase = ;

     int n,m;

     scanf("%d",&T);

     while(T--)

     {

         iCase++;

         scanf("%d%d",&n,&m);

         for(int i = ;i < m;i++)

             scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].c);

         sort(edge,edge+m,cmp1);

         memset(F,-,sizeof(F));

         int cnt = ;

         for(int i = ;i < m;i++)

         {

             int t1 = find(edge[i].u);

             int t2 = find(edge[i].v);

             if(t1 != t2)

             {

                 F[t1] = t2;

                 if(edge[i].c == )cnt++;

             }

         }

         int Low = cnt;

         memset(F,-,sizeof(F));

         sort(edge,edge+m,cmp2);

         cnt = ;

         for(int i = ;i < m;i++)

         {

             int t1 = find(edge[i].u);

             int t2 = find(edge[i].v);

             if(t1 != t2)

             {

                 F[t1] = t2;

                 if(edge[i].c == )cnt++;

             }

         }

         int High = cnt;

         bool ff = true;

         for(int i = ;i <= n;i++)

             if(find(i) != find())

             {

                 ff = false;

                 break;

             }

         if(!ff)

         {

             printf("Case #%d: No\n",iCase);

             continue;

         }

         bool flag = false;

         for(int i = ;i <= tot;i++)

             if(f[i] >= Low && f[i] <= High)

                 flag = true;

         if(flag)

             printf("Case #%d: Yes\n",iCase);

         else printf("Case #%d: No\n",iCase);

     }

     return ;

 }