역사
시간 제한1초메모리 제한128 MB
최대 400개 사건 간의 선후 관계가 주어졌을 때, 질의로 주어진 두 사건의 순서를 추이 관계로 판별할 수 있는지 답하는 문제입니다.
문제
세준이는 한국사에 해박하여 여러 역사적 사건의 전후 관계를 잘 알고 있다.
세준이가 이미 알고 있는 일부 사건들의 전후 관계가 주어진다. 각 질문에 대해, 주어진 관계들로부터 두 사건의 전후 관계를 알 수 있는지 답하는 프로그램을 작성하라.
입력
첫째 줄에 사건의 개수 n(n <= 400)과 알고 있는 전후 관계의 개수 k(k <= 50,000)가 자연수로 주어진다.
다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 주어지는 전후 관계에는 모순이 없다.
그다음 줄에는 전후 관계를 알고 싶은 사건 쌍의 수 s(s <= 50,000)가 자연수로 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다.
사건의 번호는 모두 1 이상 n 이하의 자연수이다.
출력
s개의 질문에 대해 한 줄에 하나씩 답을 출력한다.
질문에서 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났다고 알 수 있으면 -1을 출력한다. 뒤에 있는 번호의 사건이 앞에 있는 번호의 사건보다 먼저 일어났다고 알 수 있으면 1을 출력한다. 전후 관계를 알 수 없으면 0을 출력한다.