여러 학교들이 컴퓨터 네트워크로 연결이 되어 있다. 어떤 소프트웨어가 개발되어 한 학교로 왔을 때, 그 학교는 자기가 보내기로 되어 있는 다른 학교에게 그 소프트웨어를 네트워크로 전달하도록 학교 사이에 합의가 되어 있다.

이 과정을 되풀이하면 결국 모든 학교에 소프트웨어가 전달된다.

단 , A 학교의 리스트에서 나타내는 학교가 B 리스트의 학교에 반드시 나타날 필요는 없다.

이번 문제는 두 가지다.

문제1

문제2

또한 우리는 여러 학교 중 아무 한 곳에만 소프트웨어를 보내도 결국 모든 학교가 그 소프트웨어를 공급받게 하고 싶다. 그러려면 소프트웨어 공급 네트워크 망을 최소 몇 군데 더 확장해야 하는지를 계산하는 것이 둘째 문제이다. 여기서 한 군데 확장한다는 말은 어떤 학교에서 자기가 보내기로 배당된 학교에 보낼 대상 학교를 한 곳 더 추가한다는 뜻이다.

입력

각 학교는 1부터 N까지의 수로 구분한다. 그리고 다음 N줄에는 1부터 N까지 각 학교가 소프트웨어를 보내기로 되어 있는 대상 학교의 번호가 들어있다. 각각의 목록은 0으로 끝난다. 소프트웨어를 보낼 학교가 하나도 없는 학교에 해당하는 줄에는 그냥 0만 있다.

출력

첫째 줄에는 첫째 문제의 정답이 자연수로 들어간다. 둘째 줄에는 둘째 문제의 정답을 적는다.

입출력 예

입력

5               
2 4 3 0         
4 5 0
0
0
1 0

출력

1
2

보충

• 문제 1 ... 1 , 2 , 5 중 한 학교에만 보내면 모든 학교로 보낼수 있으므로 답은 1
  구현 : dfs 가능

• 문제 2 ... 3 과 4 를 1 , 2 , 3 중에 하나로 연결하면 되니 답은 2
  구현: 문제 1 + graph 를 뒤집어 놓은 후 dfs

  

출처: ioi