2015
09-18

# Fibonacci Tree

### 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 <= 105) and
M(0 <= M <= 105).
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

#include <cstdio>
#include <algorithm>

using namespace std;

struct Edge {
int s,e,c;
Edge(int ss=0,int ee=0,int cc=0):s(ss),e(ee),c(cc) {}
bool operator < (const Edge& a) const {
return c<a.c;
}
}g[100005];

int par[100005],pa,pb,f[25];

int getPar(int a) {
if(par[a]!=a)
par[a]=getPar(par[a]);
return par[a];
}

void Merge(int a,int b) {
pa=getPar(a),pb=getPar(b);
if(pa!=pb)
par[pb]=pa;
}

int main() {
int n,m,i,T,kase=0,cnt,low,hig;
bool flag;
i=1,f[0]=1,f[1]=2;
while(f[i]<100005) {
f[i+1]=f[i]+f[i-1];
++i;
}
scanf("%d",&T);
while(kase<T) {
scanf("%d%d",&n,&m);
low=hig=0,cnt=1;
for(i=0;i<m;++i)
scanf("%d%d%d",&g[i].s,&g[i].e,&g[i].c);
for(i=1;i<=n;++i)
par[i]=i;
sort(g,g+m);
for(i=0;i<m&&cnt!=n;++i) {
if(getPar(g[i].s)!=getPar(g[i].e)) {
Merge(g[i].s,g[i].e);
++cnt;
low+=g[i].c;
}
}
flag=false;
if(cnt==n) {//如果图是连通的
cnt=1;
for(i=1;i<=n;++i)
par[i]=i;
for(i=m-1;i>=0&&cnt!=n;--i) {
if(getPar(g[i].s)!=getPar(g[i].e)) {
Merge(g[i].s,g[i].e);
++cnt;
hig+=g[i].c;
}
}
i=0;
while(f[i]<low)
++i;
if(f[i]<=hig)
flag=true;
}
printf("Case #%d: %s\n",++kase,flag?"Yes":"No");
}
return 0;
}


1. 外来东西再好，都必须根据自身情况作恰当取舍，连老毛都说马列主义要和中国的具体实践相结合，我们今天更应该这样。西方要学习，照搬会水土不服，何况西方民主的弊端也已经显现，过分民主、国家弱化、扯皮政治、效率低下、强权政治、内忧外患，等等，这些都是我们要借鉴的。

2. 外来东西再好，都必须根据自身情况作恰当取舍，连老毛都说马列主义要和中国的具体实践相结合，我们今天更应该这样。西方要学习，照搬会水土不服，何况西方民主的弊端也已经显现，过分民主、国家弱化、扯皮政治、效率低下、强权政治、内忧外患，等等，这些都是我们要借鉴的。

3. 外来东西再好，都必须根据自身情况作恰当取舍，连老毛都说马列主义要和中国的具体实践相结合，我们今天更应该这样。西方要学习，照搬会水土不服，何况西方民主的弊端也已经显现，过分民主、国家弱化、扯皮政治、效率低下、强权政治、内忧外患，等等，这些都是我们要借鉴的。

4. 外来东西再好，都必须根据自身情况作恰当取舍，连老毛都说马列主义要和中国的具体实践相结合，我们今天更应该这样。西方要学习，照搬会水土不服，何况西方民主的弊端也已经显现，过分民主、国家弱化、扯皮政治、效率低下、强权政治、内忧外患，等等，这些都是我们要借鉴的。

5. 外来东西再好，都必须根据自身情况作恰当取舍，连老毛都说马列主义要和中国的具体实践相结合，我们今天更应该这样。西方要学习，照搬会水土不服，何况西方民主的弊端也已经显现，过分民主、国家弱化、扯皮政治、效率低下、强权政治、内忧外患，等等，这些都是我们要借鉴的。

6. 外来东西再好，都必须根据自身情况作恰当取舍，连老毛都说马列主义要和中国的具体实践相结合，我们今天更应该这样。西方要学习，照搬会水土不服，何况西方民主的弊端也已经显现，过分民主、国家弱化、扯皮政治、效率低下、强权政治、内忧外患，等等，这些都是我们要借鉴的。

7. 外来东西再好，都必须根据自身情况作恰当取舍，连老毛都说马列主义要和中国的具体实践相结合，我们今天更应该这样。西方要学习，照搬会水土不服，何况西方民主的弊端也已经显现，过分民主、国家弱化、扯皮政治、效率低下、强权政治、内忧外患，等等，这些都是我们要借鉴的。

8. 外来东西再好，都必须根据自身情况作恰当取舍，连老毛都说马列主义要和中国的具体实践相结合，我们今天更应该这样。西方要学习，照搬会水土不服，何况西方民主的弊端也已经显现，过分民主、国家弱化、扯皮政治、效率低下、强权政治、内忧外患，等等，这些都是我们要借鉴的。

9. 外来东西再好，都必须根据自身情况作恰当取舍，连老毛都说马列主义要和中国的具体实践相结合，我们今天更应该这样。西方要学习，照搬会水土不服，何况西方民主的弊端也已经显现，过分民主、国家弱化、扯皮政治、效率低下、强权政治、内忧外患，等等，这些都是我们要借鉴的。

10. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

11. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

12. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

13. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

14. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

15. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

16. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

17. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

18. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

19. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

20. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

21. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

22. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

23. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。

24. 5马赫的导弹打50公里外0.8马赫的飞机可完全不相当于打静止目标啊！不死鸟导弹飞到对方飞机那里去的时候，对方已经移动了3公里远了。而且导弹命中目标的关键在于最后3公里的位移，这就是为啥格斗弹都有30G以上的机动过载能力。