논리학자

완벽한 논리학자 무리가 다시 새로운 논리 퍼즐의 주인공이 되어 달라는 요청을 받았다. 이번에는 그들 중 어떤 $n$명이 참가할지 정해야 한다.

이번 논리 퍼즐은 $n$개의 노드와 $n$개의 간선을 가진 무방향 그래프에서 펼쳐진다. 각 간선은 서로 다른 두 노드를 연결하며, 어느 두 노드 사이에도 간선은 많아야 하나뿐이다. 또한 그래프는 연결되어 있다. 즉, 간선을 따라가면 어떤 노드에서든 다른 어떤 노드로도 갈 수 있다. 각 노드에는 논리학자 한 명이 위치하며, 각 논리학자는 자신의 노드와 간선으로 연결된 노드에 있는 논리학자만을 볼 수 있다.

그들은 이미 함정이 눈 색깔과 관련되어 있을 것이라고 짐작하고, 각 논리학자가 눈이 파란 사람을 정확히 한 명 보도록 배치하기로 했다. 늘 그렇듯 논리학자는 자신의 눈 색깔을 볼 수 없으므로, 눈이 파란 논리학자도 눈이 파란 사람을 정확히 한 명 보아야 한다.

요구되는 배치를 만들기 위해 필요한 눈이 파란 논리학자의 최소 수는 얼마인가?

첫째 줄에 그래프의 노드 수이자 논리학자의 수인 정수 $n$이 주어진다.

다음 $n$개 줄에는 그래프의 간선을 나타내는 정수 쌍이 주어진다. 각 간선은 서로 다른 두 노드를 연결하며, 같은 간선이 입력에 두 번 나오지 않는다.

요구되는 배치가 존재하지 않으면 첫째 줄에 -1을 출력한다.

그렇지 않으면 첫째 줄에 필요한 눈이 파란 논리학자의 최소 수를 출력한다.

모든 부분문제에서 $3 \le n \le 100\,000$이다.

첫 번째 예제 해설: 눈이 파란 논리학자는 예를 들어 노드 1과 2에 있는 사람일 수 있다.

두 번째 예제 해설: 논리학자 한 명만 눈이 파랗다면 그 사람은 눈이 파란 다른 사람을 볼 수 없다. 눈이 파란 사람이 둘 이상이라면 누군가는 눈이 파란 사람을 둘 이상 보게 된다.