Game of Death
Time limit3sMemory limit256 MB
Given a directed graph where each of N people points to two others, determine for M queries if b can be reached from a in exactly K steps.
- Level
Medium6 of 10
- Topics
- Graph, Matrix, Binary search
- Solved
- No attempts yet
Problem
N people sit in a circle, numbered from 1 to N.
Each person points to two people at the same time, one with each hand. A person cannot point to themself, but both hands may point to the same other person. The starting person chooses one of the two people they point to. The chosen person then chooses one of the two people they point to, and the process continues. After K choices, the K-th chosen person is caught.
You are given N, K, and the two people pointed to by each person. For each query, decide whether person b can be the K-th chosen person when person a starts and every choice is made appropriately.
Input
The first line contains three integers N(2 <= N <= 200), K(1 <= K <= 1,000,000), and M(1 <= M <= 1,000,000).
Each of the next N lines contains the two people pointed to by one person. The next M lines each contain one query a and b.
Output
For each query in input order, print death if person b can be the K-th chosen person when person a starts. Otherwise, print life.