Coding 공부

import sys
input = sys.stdin.readline
def check(num):
    visited[num] = True
    stack = [num]
 
    while stack:
        node = stack.pop(0)
 
        for next_node in tree[node]:
            if tree[node][next_node] == 1:
                if not visited[next_node]:
                    visited[next_node] = True
                    stack.append(next_node)
                    tree[node][next_node] = 0
                    tree[next_node][node] = 0
                else:
                    return False
    return True
            
 
 
tc = 1
while True:
    N,M = map(int,input().split())
    if N+M == 0:
        break
    parent_cnt = [0]*(N+1)
    tree = [{} for _ in range(N+1)]
    for _ in range(M):
        x,y = map(int,input().split())
        tree[x][y] = 1
        tree[y][x] = 1
    cnt = 0
    visited = [False]*(N+1)
    for num in range(1,N+1):
        if not visited[num]:
            if check(num):
                cnt += 1
    if cnt == 0:
        print(f'Case {tc}: No trees.')
    elif cnt == 1:
        print(f'Case {tc}: There is one tree.')
    else:
        print(f'Case {tc}: A forest of {cnt} trees.')
 
 
    tc += 1

import sys
import collections
input = sys.stdin.readline
 
def bfs1(x):
    que=collections.deque()
    que.append(x)
    temp=set()
    temp.add(x)
    while que:
        node=que.popleft()
        for i in graph1[node]:
            if i not in temp:
                temp.add(i)
                visit[x]+=1       
                que.append(i)
    return
def bfs2(x):
    que=collections.deque()
    que.append(x)
    temp=set()
    temp.add(x)
    while que:
        node=que.popleft()
        for i in graph2[node]:            
            if i not in temp:
                temp.add(i)
                visit[x]+=1       
                que.append(i)
    return
 
 
N,M = map(int,input().split())
arr=[list(map(int,input().split())) for i in range(M)]
graph1=[[] for i in range(N+1)]
graph2=[[] for i in range(N+1)]
for i in arr:
    graph1[i[0]].append(i[1])
    graph2[i[1]].append(i[0])
visit=[0]*(N+1)
for i in range(1,N+1):        
    bfs1(i)
    bfs2(i)
 
cnt=visit.count(N-1)
print(cnt)