문제

Input1)
4 4 5
1 2
1 3
2 4
3 4
1 1
1 2
1 3
2 1
1 4
Output1)
King-God-Emperor
Input2)
3 2 2
1 2
2 3
1 1
2 2
Output2)
Lier!
Input3)
3 2 5
1 2
2 3
1 1
1 2
1 2
2 2
1 3
Output3)
King-God-Emperor

Point

치트키일 경우

• 1(짓는 정보) - 부모 건물이 하나라도 없을 때
  : 지은 개수가 0인 부모가 존재
• 2(파괴 정보) - 없는 건물이 파괴 됐을 때

부모 건물이 여러개 일 수 있다.

• 부모 건물이 여러개 인 경우 "모든" 부모건물이 있어야 자식 건물을 지을 수 있다.

변수

• pars : 각 건물의 부모 건물 종류를 저장
• built_now : 각 건물 마다 현재 지어져 있는 개수를 저장
  • 0인데 명령어 2로 파괴했다고 하면 치트키 쓴거임.
• can_build : 부모 건물이 애초에 없는 건물은 마음대로 지을 수 있으므로, 그 정보를 저장. 1이면 부모 건물 없음. 0이면 부모 건물 존재.
• par_min : 어떤 건물의 부모 건물 중 지어진 개수가 0인 것이 있으면 지을 수 없다. 그러므로 각 부모 건물의 지어진 개수 중 최소값을 계산.
  • (명령어 1) 지은 건물이 부모가 있는 건물인데(can_build==0), 부모 중 지어진 개수가 0인 부모가 있으면(par_min==0) 치트키 쓴거임.

전체코드

n, m, k = [int(x) for x in input().split()]

pars = [[] for _ in range(n + 1)]

built_now = [0] * (n + 1)
can_build = [1] * (n + 1)

for i in range(m):
    p, c = [int(x) for x in input().split()]
    pars[c].append(p)
    can_build[c] = 0


def main():
    for i in range(k):
        c, b = [int(x) for x in input().split()]
        if c == 1:
            par_min = 100000
            for p in pars[b]:
              par_min = min(par_min, built_now[p])
            if can_build[b]==0 and par_min == 0:
                return i
            built_now[b] += 1
        else:
            if built_now[b] == 0:
                return i
            built_now[b] -= 1
        # print(f"i : {i}")
        # print(built_now)
    return -1


asw = main()

if asw == -1:
    print("King-God-Emperor")
else:
    for i in range(k - asw - 1):
        input()
    print("Lier!")