어떤 특이한 개미종은, 방이 정점이고 터널이 간선인 개미굴을 만들고 각 방에 음식인 견과류를 저장한다.

이 종은 공기 흐름을 위해 견과류보다 살짝 큰 크기의 방을 만들고, 딱 맞는 크기의 터널을 만든다.

따라서, 공기 흐름을 위해 터널에는 견과류를 놔두면 안된다.

견과류가 있는 방에 들어가려면 터널을 통해 견과류를 인접한 방으로 밀어내야 한다.

개미가 나온 방 외에 다른 인접한 방이 비어 있지 않으면 견과류를 밀어낼 수 없으므로, 개미가 방에 들어갈 수 없다.

주어진 개미굴에 대하여, 개미들이 입구인 1번 정점으로부터 들어갈 수 있는 방의 개수를 구하여라.

개미가 처음에 있는 방(입구)에는 견과류가 없으며, 개미굴에는 사이클이 없음이 보장된다.

개미굴 timer 3s memory 1024MB

개미굴 3s 1024MB