| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1411
炸死萌萌
Time Limit: 1000ms
Memory Limit: 65536kb Description
萌萌背叛了组织！组织决定派你去炸死他.经过精心的策划，萌萌终于被你勾引到了一个迷宫里，这个迷宫可以视为一个有n个节点、m条边的无向图，节点编号0到n-1。萌萌被困在了这个迷宫里。萌萌每天白天必然在某个节点上，你不知道他在哪里，但是你知道萌萌在每天晚上一定会从他当前所在节点沿着某条边移动到另一个节点上。你在这个图的每个节点都装上了遥控炸弹，但是由于技能冷却时间等一系列坑爹问题，你每天白天只能引爆一个节点上的炸弹，如果萌萌当天恰好位于这个节点上，那么他就成功的被你炸死了。但是这种炸弹可以再生，所以你可以对同一个节点引爆多次. 现在你想知道，对于这个迷宫，你能不能在有限的时间内将萌萌炸死. Input
第一行T表示数据组数对于每组数据，第一行两个整数n,m 接下来m行，每行两个数a,b表示点a与点b之间有一条边 数据规模有T<=10000 n<=20 图中不包括自环与重边 输入数据保证图为连通图 Output
每组输入数据对应一行输出，输出YES如果你能在有限时间内将萌萌炸死，否则输出NO
Sample Input
2 5 4 0 1 1 2 2 3 3 4 5 5 0 1 1 2 2 3 3 4 4 0 Sample Output
YES NO Hint
对于第一组数据是一条链，只要沿着0123401234的顺序引爆，无论萌萌在哪里都会被炸死Source
haiwei624 & renne
|