따스나라에는 개의 정점으로 이루어진 포레스트가 있다. 정점에는 의 번호가 붙어 있다. 각 정점에는 따스가 한 명씩 서 있다.
정점 에 서 있는 따스는 에 인접한 모든 간선을 볼 수 없다. 그 밖의 모든 간선과 정점 번호는 볼 수 있다. 모든 따스는 다음 사실을 알고 있다.
어느 날 다다스가 모든 따스에게 다음 사실을 공개적으로 선언했다.
이 포레스트에는 간선이 하나 이상 존재한다.
그 후 날짜를 일부터 세기 시작한다. 매일 모든 따스는 이전 날까지의 모든 선언을 이용하여 동시에 다음 둘 중 하나를 공개적으로 선언한다.
같은 날에 이루어진 다른 따스의 선언은 그날의 판단에 사용할 수 없다. 모든 선언은 이후 모든 따스에게 공개된다.
실제 포레스트의 구조가 주어진다. 자신의 정점에 인접한 간선이 하나 이상 존재한다는 것을 아는 따스가 처음으로 등장하는 날짜를 구하여라.
입력은 다음과 같은 형식으로 주어진다.
case case
각 테스트 케이스마다, 조건을 만족하는 최소 날짜를 한 줄에 출력한다.
각 케이스는 다음과 같은 형식으로 주어진다.
각 에 대해 번 정점과 번 정점을 잇는 무향 간선이 존재한다.
