아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

영향력

시간 제한3초메모리 제한128 MB

요약
후보 집합 X 중에서 영향 관계로 도달하는 사람이 가장 많은 사람을 고르고 동점이면 번호가 가장 작은 사람을 출력합니다.
난이도

보통10점 중 6점

유형
위상 정렬, 그래프, 비트 연산
정답자
아직 제출이 없습니다

문제

어떤 사회에나 사람 사이의 영향 관계가 있다. 사람 x가 다른 사람 y에게 영향을 줄 수 있다는 뜻이다. 소프토피아도 마찬가지인데, 이 사회의 영향 관계는 추이적이다. x가 y에게 영향을 주고 y가 z에게 영향을 주면 x도 z에게 영향을 준다. 또 이 사회의 규칙에 따라 x가 다른 사람 y에게 영향을 주면 y는 x에게 영향을 줄 수 없다. 그래서 소프토피아의 어떤 사람 x가 무언가를 원하면 x의 영향을 받는 사람은 모두 같은 것을 원하게 된다.

소프토피아는 거의 완벽한 사회지만, 이 영향 관계를 타고 거짓 요구를 퍼뜨릴 사람의 집합 X가 있다. 그리고 자기 요구를 퍼뜨리려고 X에서 누구를 골라야 할지 알아내려는 악한 존재도 있다. 사회는 X에서 한 사람만 고를 수 있으므로, 소프토피아에서 가장 많은 사람에게 영향을 줄 수 있는 사람을 고르려 한다. 조건을 만족하는 사람이 둘 이상이면 번호가 가장 작은 사람을 고른다.

입력

첫째 줄에 정수 두 개가 공백 하나로 구분되어 주어진다. 사회 구성원의 수 nn (n≤5000n \le 5000)과 집합 X의 원소 개수 kk다. 둘째 줄에는 X의 원소, 즉 1 이상 nn 이하의 서로 다른 정수 kk개가 공백으로 구분되어 주어진다. 이어서 nn개의 줄이 주어진다. 각 줄은 그 줄이 설명하는 사람의 번호로 시작하고, 그 뒤에 그 사람이 직접 영향을 주는 사람의 번호가 공백으로 구분되어 이어진다. 사람의 번호는 1부터 nn까지다. 사회 전체의 영향 관계 수는 250000보다 적다. 입력에 들어 있는 여분의 공백은 무시한다.

출력

위 조건을 만족하는 사람의 번호를 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    5 2
    1 2
    1 3 4
    2 3 4
    3 5
    4 5
    5
    
    예상 출력
    1
    
  2. 예제 2

    입력
    6 3
    1 2 3
    1 2
    2 5
    3 4 2
    4 6
    5
    6
    
    예상 출력
    3