이걸로 더 이상 무섭지 않지?
노아는 세계적인 스트리트 아티스트로, 그녀의 시그니처인 나비 그림은 특히 아름답기로 유명하다.
이번에 노아는 캔버스 위에 한 폭의 그림을 그리려고 한다. 는 정점 개, 간선 개로 이루어진 무향 단순 연결 그래프이다. 처음에 캔버스의 모든 정점은 붉게 물들지 않은 상태이다.
위 그림과 동형인 의 부분그래프 중 이를 이루는 개의 정점이 모두 붉게 물든 것을 라고 한다.
첫째 줄에 그래프의 정점의 개수 과 간선의 개수 이 공백을 사이에 두고 주어진다.
개의 정수 을 공백을 사이에 두고 출력한다. 는 개의 정점이 붉게 물든 이후 그래프에 존재하는 붉은 나비의 개수이다.
모든 정점이 붉게 물들면 개의 붉은 나비가 존재하게 된다.
위는 개의 정점이 붉게 물든 상태의 그림으로, 개의 붉은 나비가 존재한다.
모든 정점은 정해진 순서대로 붉게 물들게 된다. 정점이 물들 때마다 캔버스에 그려진 붉은 나비의 개수를 세어 보자.
단순 그래프의 정의
동일한 정점 와 를 연결하는 간선이 없고, 두 정점 사이를 연결하는 간선이 최대 개인 그래프를 단순 그래프라고 한다.
동형의 정의
두 그래프 과 의 정점 사이에 일대일 대응 가 존재하고, 이 대응에서 임의의 에 대해 이면 두 그래프는 동형이라고 한다. 즉, 정점의 번호를 적절히 바꾸면 두 그래프의 정점과 간선이 완전히 일치해야 한다.
부분그래프의 정의
그래프 에서 일부 정점 와 일부 간선 를 선택하자. 에 속한 모든 간선의 양 끝점이 모두 에 속할 때, 그래프 를 의 부분그래프라고 한다.
다음 개의 줄에 번째 간선이 연결하는 두 정점의 번호 가 공백을 사이에 두고 주어진다.
다음 줄에 정점이 붉게 물드는 순서를 나타내는 길이가 인 순열 이 공백을 사이에 두고 주어진다. 는 번째로 물드는 정점의 번호를 의미한다.
입력으로 주어지는 그래프는 단순 연결 그래프임이 보장된다.
