2099번

수정 전

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

문제

  The game of death는 확률성과 함께 전략이 요구되는 게임인데, N명의 사람들이 원을 이루고 모여 앉은 후 시작된다. 사람들에게는 1번부터 N번까지 번호가 매겨져 있다고 하자.

  각 사람은 자신의 양 손을 이용해서 동시에 두 명의 사람을 가리킨다. 자기 자신은 가리킬 수 없으나 자신이 가리키는 두 사람이 꼭 다를 필요는 없다. 그리고 첫 사람이 자연수 K를 하나 정한 뒤에, 자신의 가리키고 있는 두 사람 중 한 사람을 지목한다. 첫 번째로 지목된 사람은 마찬가지로 자신이 가리키고 있는 두 사람 중 한 사람을 지목한다. 마찬가지로 지목된 사람이 같은 방법으로 사람들 지목해 나가며, K번째로 지목된 사람이 걸리게 되는 게임이다.

  예를 들어 N=4이고 K=2인 경우를 생각해 보자. 1번 사람은 2번과 4번 사람을 지목했고, 2번 사람은 1번과 3번을, 3번 사람은 1번과 4번을, 그리고 4번 사람은 2번과 2번을 지목했다고 하자. 4번 사람이 시작했을 때 1번이 걸릴 수 있으나, (4->2->1) 1번 사람이 시작했을 때는 4번 사람이 걸릴 수 없다.

  N과 K, 그리고 각 사람이 지목한 두 사람에 대한 정보가 주어졌을 때, a번 사람이 시작했을 때 b번 사람이 걸리는 경우가 있는지 없는지를 알아내는 프로그램을 작성하시오. a와 b의 쌍은 M개 주어진다.

입력

  첫째 줄에 두 정수 N(2<=N<=200)과 K(1<=K<=2,000)와 M(1<=M<=1,000,000)이 주어진다. 다음 N개의 줄에 걸쳐 각 사람이 지목한 두 명의 사람이 번호로 주어진다. 다음 M개의 줄에 걸쳐 각 줄에 a와 b가 주어진다.

출력

  M개의 줄에, 입력받은 순서대로 a번 사람으로 시작해서 b번 사람이 걸리는 경우가 있으면 'death'를, 걸리게 할 수 없으면 'life'를 출력한다.

예제 입력

4 2 3 2 4 1 3 4 1 2 2 4 1 1 4 1 1

예제 출력

death life death

힌트

수정 후

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

문제

  The game of death는 확률성과 함께 전략이 요구되는 게임인데, N명의 사람들이 원을 이루고 모여 앉은 후 시작된다. 사람들에게는 1번부터 N번까지 번호가 매겨져 있다고 하자.

  각 사람은 자신의 양 손을 이용해서 동시에 두 명의 사람을 가리킨다. 자기 자신은 가리킬 수 없으나 자신이 가리키는 두 사람이 꼭 다를 필요는 없다. 그리고 첫 사람이 자연수 K를 하나 정한 뒤에, 자신의 가리키고 있는 두 사람 중 한 사람을 지목한다. 첫 번째로 지목된 사람은 마찬가지로 자신이 가리키고 있는 두 사람 중 한 사람을 지목한다. 마찬가지로 지목된 사람이 같은 방법으로 사람들 지목해 나가며, K번째로 지목된 사람이 걸리게 되는 게임이다.

  예를 들어 N=4이고 K=2인 경우를 생각해 보자. 1번 사람은 2번과 4번 사람을 지목했고, 2번 사람은 1번과 3번을, 3번 사람은 1번과 4번을, 그리고 4번 사람은 2번과 2번을 지목했다고 하자. 4번 사람이 시작했을 때 1번이 걸릴 수 있으나, (4->2->1) 1번 사람이 시작했을 때는 4번 사람이 걸릴 수 없다.

  N과 K, 그리고 각 사람이 지목한 두 사람에 대한 정보가 주어졌을 때, a번 사람이 시작했을 때 b번 사람이 걸리는 경우가 있는지 없는지를 알아내는 프로그램을 작성하시오. a와 b의 쌍은 M개 주어진다.

입력

  첫째 줄에 두 정수 N(2<=N<=200)과 K(1<=K<=1,000,000)와 M(1<=M<=1,000,000)이 주어진다. 다음 N개의 줄에 걸쳐 각 사람이 지목한 두 명의 사람이 번호로 주어진다. 다음 M개의 줄에 걸쳐 각 줄에 a와 b가 주어진다.

출력

  M개의 줄에, 입력받은 순서대로 a번 사람으로 시작해서 b번 사람이 걸리는 경우가 있으면 'death'를, 걸리게 할 수 없으면 'life'를 출력한다.

예제 입력

4 2 3 2 4 1 3 4 1 2 2 4 1 1 4 1 1

예제 출력

death life death

힌트