27306번 - DAGame

우"영"이와 현"철"이는 영철버거 돈 마리네 세트를 걸고 내기를 한다. 현철이는 다음과 같은 게임을 만들었다.

$N$개의 노드와 $M$개의 간선으로 이루어진 DAG(사이클이 없는 방향그래프)가 있다. $K$개의 말이 각각 노드 중 하나에 놓여 있다. 모든 노드마다 놓일 수 있는 말의 개수에는 제한이 없다. 각 말은 색깔이 있으며, $1$이상 $N$이하의 정수로 표현된다. 모든 색깔에 대하여 특정 색깔을 가진 말은 최대 두개뿐이다. 우영이부터 차례를 번갈아가며 다음 행동을 취한다. 한 개의 말을 선택하여 그래프 상에서 나가는 방향의 간선을 골라 다음 노드로 옮긴다. 이때, 같은 색깔의 말이 같은 노드에 존재하는 순간 서로 업혀 그 다음부터 같이 움직이게 되고, 색이 다른 말끼리는 항상 영향을 주지 않는다. 게임 시작 전부터 말이 업히는 경우가 존재할 수도 있다. 자신의 차례에 더 이상 행동을 할 수 없는 사람이 지게 된다. 초기의 그래프와 말의 정보가 주어지고 우영이와 현철이는 자신의 차례에서 최선을 다할 때, 둘 중 누가 게임을 이기는지 출력하시오.

첫 번째 줄에 노드의 개수를 나타내는 정수 $N$ ($2 \le N \leq 500$), 간선의 개수를 나타내는 정수 $M$ ($1 \leq M \leq 100\,000$)이 주어진다.

두 번째 줄 부터 $M$개의 줄에 서로 다른 두 정수 $p$, $q$ ($1 \leq p$, $q \leq N$)가 주어지며 이는 $p$번 노드에서 $q$번 노드로 가는 간선이 존재한다는 것을 뜻한다. 어떤 $p$와 $q$에 대해서 $p$번 노드와 $q$번 노드를 잇는 동일한 간선이 여러 번 주어질 수도 있다.

그 다음 줄에는 말의 개수를 나타내는 정수 $K$가 주어진다. ($1 \leq K \le 2\cdot N$)

그 다음 줄 부터 $K$개의 줄에 두 정수 $v_i$, $c_i$ ($1 \leq i \leq K$)가 주어지며 이는 $i$번 말이 색깔이 $c_i$이고 $v_i$번 노드에 놓여 있는 것을 뜻한다. ($1 \leq v_i, c_i \leq N$)

주어지는 그래프는 DAG임이 보장된다.

우영이가 게임에서 이기면 "Young"을 출력하고, 현철이가 게임에서 이기면 "Cheol"을 출력한다.