- #include#include#include using namespace std;#define M 100010#define N 210 inline int min(int a, int b) {
- return aa: b;
- }
- inline int 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;
- }
- int get() {
- int x;
- char c = getchar();
- while (c != 'm' && c != 'h') c = getchar();
- if (c == 'm') x = read() * 2;
- else x = read() * 2 - 1;
- return x;
- }
- struct ljn {
- int fro,
- to;
- }
- e[M];
- int n,
- m,
- t,
- t1,
- t2,
- lj[N],
- cnt,
- qwe,
- dfn[N],
- low[N],
- q[N],
- tq,
- num[N],
- tot;
- bool vs[N];
- inline void add(int a, int b) {
- cnt++;
- e[cnt].fro = lj[a];
- e[cnt].to = b;
- lj[a] = cnt;
- }
- void tarjan(int x) {
- vs[x] = 1;
- q[++tq] = x;
- dfn[x] = low[x] = ++qwe;
- for (int i = lj[x]; i; i = e[i].fro) {
- int et = e[i].to;
- if (!dfn[et]) {
- tarjan(et);
- low[x] = min(low[x], low[et]);
- } else if (vs[et]) low[x] = min(low[x], dfn[et]);
- }
- if (dfn[x] == low[x]) {
- tot++;
- int now = 0;
- while (now != x) {
- now = q[tq--];
- num[now] = tot;
- vs[now] = 0;
- }
- }
- }
- int main() {
- t = read();
- while (t--) {
- memset(dfn, 0, sizeof(dfn));
- memset(low, 0, sizeof(low));
- memset(vs, 0, sizeof(vs));
- memset(lj, 0, sizeof(lj));
- memset(num, 0, sizeof(num));
- n = read();
- m = read();
- int x,
- y,
- xp,
- yp;
- for (int i = 0; i) {
- x = get();
- y = get();
- if (x % 2 == 0) xp = x--;
- else xp = x++;
- if (y % 2 == 0) yp = y--;
- else yp = y++;
- add(xp, y);
- add(yp, x);
- }
- tot = tq = qwe = 0;
- for (int i = 1; i <= n * 2; i++) if (!dfn[i]) {
- tarjan(i);
- }
- bool f = 1;
- for (int i = 1; i <= n; i++) if (num[i * 2] == num[i * 2 - 1]) {
- f = 0;
- break;
- }
- if (f) puts("GOOD");
- else puts("BAD");
- }
- }
来源: http://www.bubuko.com/infodetail-1955364.html