시간 제한
메모리 제한
시간 제한
1초
메모리 제한
128 MB
당신은 새로 지은 스키장을 점검하는 팀을 이끌고 있다. 스키장은 여러 개의 산에 걸쳐 있으며 여러 개의 슬로프로 이루어져 있다. 슬로프들은 서로 갈라지고 합쳐지며 이어지고, 스키장 전체 지도는 방향 비순환 그래프로 나타낼 수 있다. 그래프의 정점은 스키장의 지점을 뜻하고, 각 방향 간선은 언제나 아래로 내려가는 슬로프를 뜻한다.
당신의 팀은 모든 슬로프를 점검해야 한다. 아직 리프트는 운행하지 않지만 헬리콥터가 한 대 있다. 헬리콥터는 한 번 비행할 때마다 점검 요원 한 명을 스키장의 임의의 지점에 내려 줄 수 있다. 내린 지점에서 요원은 슬로프를 따라 아래로 내려가며 지나가는 모든 슬로프를 점검한다. 같은 슬로프를 여러 번 점검해도 되지만, 헬리콥터 비행은 비용이 크므로 되도록 적은 횟수의 비행으로 모든 슬로프를 점검해야 한다.
모든 슬로프를 점검하기 위해 필요한 최소 헬리콥터 비행 횟수를 구하여라.
첫째 줄에 지점의 개수 n (2≤n≤100)이 주어진다.
이어지는 n개의 줄에는 1번부터 n번까지 번호가 매겨진 각 지점의 정보가 주어진다. 그중 i번째 줄은 정수 mi (0≤mi<n)로 시작하고, 이어서 서로 다른 mi개의 정수 ai,1,…,ai,mi (1≤ai,j≤n, ai,j=i)가 주어진다. 이는 지점 i에서 지점 ai,j로 내려가는 슬로프가 있음을 뜻한다.
모든 지점에는 적어도 하나의 슬로프가 연결되어 있다.
모든 슬로프를 점검하는 데 필요한 최소 헬리콥터 비행 횟수를 정수 하나로 출력한다.