99342024-03-18 23:48:5042Fertőzési sorozat (50 pont)python3Accepted 50/50141ms14828 KiB
# O(N*(N+M))

from sys import stdin
input=stdin.readline

def solv():
    N,M,K = [int(x) for x in input().split()]
    F = [int(x)-1 for x in input().split()]
    graph=[[] for i in range(N)]
    for i in range(M):
        A,B = [int(x) for x in input().split()]
        graph[A-1].append(B-1)
        graph[B-1].append(A-1)
    #print(graph,N,M,K,F)

    def teszt(v):
        #print('v:',v)
        seen=[0]*N
        seen[v]=1
        cur=[v]
        index=0
        if F[0]==v:
            index=1
        while cur:
            #print('cur:',cur,index)
            tmp=set()
            for v in cur:
                for w in graph[v]:
                    if seen[w]==0:
                        seen[w]=1
                        tmp.add(w)
            oldindex=index
            while index<K and F[index] in tmp:
                index+=1
            #print('tmp:',tmp,oldindex,index)
            if index==K:
                return True
            if index==oldindex and oldindex!=0:
                return False
            if oldindex!=0 and index!=oldindex+len(tmp):
                return False
            cur=tmp
        return False
    
    res=''
    db=0
    for i in range(N):
        if teszt(i):
            db+=1
            res+=str(i+1)+' '
    print(db)
    print(res)
    
solv()
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/017ms11380 KiB
2Accepted0/018ms12032 KiB
3Accepted0/039ms11924 KiB
4Accepted2/217ms12024 KiB
5Accepted2/224ms11936 KiB
6Accepted2/237ms12392 KiB
7Accepted2/235ms12352 KiB
8Accepted2/237ms12632 KiB
9Accepted2/239ms12976 KiB
10Accepted2/2128ms13392 KiB
11Accepted1/120ms13364 KiB
12Accepted2/264ms13300 KiB
13Accepted2/275ms13176 KiB
14Accepted2/282ms13476 KiB
15Accepted2/246ms13684 KiB
16Accepted2/279ms13664 KiB
17Accepted2/2108ms13936 KiB
18Accepted1/1108ms13916 KiB
19Accepted1/163ms13784 KiB
20Accepted1/146ms13940 KiB
21Accepted1/1120ms14140 KiB
22Accepted1/1108ms14588 KiB
23Accepted1/1112ms14432 KiB
24Accepted1/1123ms14212 KiB
25Accepted1/1138ms14028 KiB
26Accepted1/1133ms14100 KiB
27Accepted1/1136ms13992 KiB
28Accepted1/197ms14216 KiB
29Accepted1/1114ms14320 KiB
30Accepted1/1103ms14336 KiB
31Accepted1/1104ms14140 KiB
32Accepted1/1136ms14616 KiB
33Accepted1/1112ms14428 KiB
34Accepted1/1141ms14736 KiB
35Accepted1/1112ms14828 KiB
36Accepted1/1120ms14820 KiB
37Accepted1/1115ms14736 KiB
38Accepted1/1108ms14828 KiB
39Accepted1/1118ms14796 KiB
40Accepted1/1136ms14780 KiB