提出 #75459440

---

ソースコード 拡げる

t=int(input())
for test in range(t):
    n,m=map(int,input().split())
    g=[[i] for i in range(n)]
    for i in range(m):
        u,v=map(int,input().split())
        u-=1
        v-=1
        g[u].append(v)
        g[v].append(u)
    w=int(input())
    s=[input() for i in range(n)]#s[都市][日付]
    vg=[[0 for i in range(n)] for k in range(w+1)]#vg[日付][都市]
    for i in range(n):
        if s[i][-1]=="x":
            vg[-1][i]=0
            continue
        vg[-1][i]=int(1<<i)
    
    for i in range(w):
        for v in range(n):
            if s[v][i]=="x":
                vg[i][v]=0
                continue
            for pv in g[v]:
                if vg[i-1][pv]:
                    vg[i][v]|=vg[i-1][pv]
        
    
    for i in range(n):
        if (vg[w-1][i]>>i)&1:
            print("Yes")
            break
    else:
        print("No")

        

提出情報

ジャッジ結果