Celebrity
시간 제한1초메모리 제한1024 MB
정점 5개짜리 단순 그래프가 최대 10000개 주어질 때, 동형인 그래프가 자기 하나뿐인 그래프의 수를 센다.
문제
잊지마 넌 흐린 어둠 사이 왼손으로 그린 별 하나
보이니 그 유일함이 얼마나 아름다운지 말야
You are my celebrity
- 아이유, Celebrity 中
별은 개의 정점으로 이루어진 단순 그래프의 별명이다. (그래프 이론에서의 star graph와는 다르다)
어떤 별 의 연결 관계를 유지한 채 정점을 적당히 이동시키거나 회전하여 별 와 같은 모양으로 만들 수 있다면 와 는 같은 별이다. 예를 들어, 아래 이미지의 첫 번째 별과 두 번째 별은 같지만 세 번째 별은 다르다.
찬우는 왼손으로 별을 개 그리고 각 별마다 부터 까지의 번호를 붙여 준 뒤, 한 번만 그려진 유일한 별들을 아름답다고 정의하였다. 찬우가 그린 별 개가 주어질 때 아름다운 별의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 이 주어진다.
둘째 줄부터 찬우가 그린 개의 별이 번 별부터 번 별까지 하나씩 주어진다.
각 별을 나타내는 데이터의 첫 줄에는 별의 간선 수 가 주어지며, 이후 줄에 걸쳐 별의 연결 관계를 나타내는 두 정수 와 가 공백으로 구분되어 주어진다. 이는 번 정점과 번 정점이 연결되어 있다는 의미이다. 별의 각 정점은 부터 까지 번호가 매겨져 있지만, 두 별이 같은지 판단할 때는 정점의 번호를 고려하지 않는다.
출력
첫째 줄에 아름다운 별의 수를 출력한다.
제한
- 각 별에서 임의의 두 정점을 잇는 간선은 최대 하나 존재한다.