만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

훌륭한 강의

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

요약
각 학생이 아는 참과 거짓 명제를 바탕으로, 강의에서 발표된 함의 관계가 학생의 지식과 처음 모순되는 순간을 찾습니다.
난이도

보통10점 중 7점

유형
그래프, 분할 정복, DFS
정답자
아직 제출이 없습니다

문제

어느 유명한 대학에는 중요한 인사들이 흥미로운 강의를 자주 하러 온다. 강의는 보통 'AA이면 BB이다' 꼴의 연역적 추론이 차례로 이어지는 형태다. 거의 모든 사람은 논리적으로 생각할 수 있다. 예를 들어 AA이면 BB이고 BB이면 CC라고 알고 있다면, AA이면 CC라고 결론 내려도 된다. 강사는 의미 없는 추론을 싫어해서 같은 명제를 두 번 말하지 않는다. 즉 'AA이면 BB'와 'CC이면 BB'처럼 결론이 같은 추론은 나오지 않는다.

강의에 몇 명의 학생이 왔다. 각 학생은 이미 세상에 대한 지식을 가지고 있다. 어떤 명제는 거짓이라고 알고 있고, 어떤 명제는 참이라고 알고 있다. 강의 중 강사는 추론을 하나씩 전한다. 그중 어느 추론은 학생의 지식과 모순될 수 있다. 예를 들어 학생이 AA를 거짓, BB를 참으로 알고 있는데 강사가 'BB이면 AA이다'라고 말하면 모순이 생긴다. 각 학생에 대해, 강사의 추론이 처음으로 학생의 지식과 모순을 일으키는 순간을 구하라. 모순이란 학생이 참이라고 여기는 명제들과 강사의 추론으로부터 학생이 거짓이라고 여기는 명제를 논리적으로 도출할 수 있는 순간을 말한다.

강의 예를 하나 보자. 강사가 'AA이면 BB', 'CC이면 DD', 'BB이면 CC'를 차례로 전했고, 학생이 AA를 참, DD를 거짓으로 알고 있다고 하자. 학생은 첫 추론을 듣고 BB가 참이라고 생각한다. 두 번째 추론 뒤에는 모순이 없다. 세 번째 추론 'BB이면 CC'를 들으면 CC가 참이라고 생각하고, 두 번째 추론을 이용해 DD가 참이라고 도출한다. 이는 DD가 거짓이라는 지식과 충돌한다. 반면 AA를 거짓, DD를 참으로 아는 다른 학생에게는 어떤 순간에도 모순이 생기지 않는다. 모든 추론을 들은 뒤에도 참인 명제에서 거짓인 명제를 도출할 수 없기 때문이다.

예제2

  1. 예제 1

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

  2. 예제 2

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