곧 다가올 2차 정기시험에 대비해, 경기과학고등학교의 번부터 번까지 총 명의 학생들은 열심히 시험공부를 하고 있다. 또한 경곽의 학생들은 친구 관계가 돈독해서, 친구인 학생끼리는 서로 돕는다. 그러한 친구 관계는 총 개 있다.
그러던 어느 날 서준이는 민기에게 ✧ ✦ 시 험 운 의 불 씨 ✦ ✧를 전해주었다! 이를 받은 착한 민기는 많은 학생들에게 불씨를 다시 전달해서 학생들이 시험을 잘 볼 수 있도록 하려고 한다. 이때 주변 학생들은 다 받았는데 자신만 못 받으면 억울하니, 민기는 두 정수 을 골라 번부터 번까지의 학생이 모두 불씨를 받게 하고자 한다. 이때 이다.
경곽의 다른 학생들도 민기와 마찬가지로 착하기 때문에, 불씨의 전달은 다음과 같이 진행된다.
동시에 여러 불씨를 전달받으면, 시간 뒤에 각 불씨를 독립적으로 전해 준다. 즉, 각 불씨에 대해 제외되는 친구는 바로 그 불씨를 전달해 준 친구뿐이다. 따라서 같은 학생에게 여러 개의 불씨를 동시에 전해줄 수도 있고, 직전에 불씨를 전달해 준 친구에게 다시 전해줄 수도 있다.
이 과정을 거쳐 모든 명의 학생이 불씨를 한 번 이상 전달받아야 한다. 또한 시험이 얼마 남지 않았으므로 불씨 전달은 시간 이하에 완전히 끝나야 한다. 즉, 시간부터는 누구도 불씨를 전달받지 않아야 한다.
이것이 가능하도록 하는 순서쌍 의 개수를 구하여라.
입력은 다음과 같은 형식으로 주어진다.
첫 번째 줄에 문제의 정답을 출력한다.
각 에 대해 는 서로 친구인 두 학생의 번호이다. 같은 친구 관계는 여러 번 주어지지 않으며, 자기 자신과 친구일 수는 없다.
