lighter   3년 전

원제: Gra
의역 제목: 훈이와 짱구의 게임

문제:
훈이는 짱구와 보드 게임 하는 것을 좋아합니다.
보드 게임에 사용되는 판은 '칸'들과, 그 '칸'들을 잇는 단방향 간선들로 이루어져 있습니다.
훈이가 가지고 있는 모든 보드 게임들은 공통적으로 '칸'들을 두 번 이상 지날 수 없다는 특징을 가지고 있습니다.

불행하게도, 훈이와 짱구는 훈이가 가지고 있는 모든 게임들을 매우 잘 알고 있어서 더 이상 재밌게 즐길 수 없습니다. 그래서 훈이는 보드 게임을 새롭게 즐길 아이디어를 하나 고안해냈습니다.

훈이의 아이디어는 다음과 같습니다.
훈이는 자신의 보드게임 컬렉션 중 아무거나 두 개를 뽑아서 '동시에' 게임을 진행 합니다.
그리고 각각의 보드게임 마다, 말을 하나씩 놓습니다.
그리고 나서 훈이와 짱구가 서로 턴을 주고 받으며 말을 움직입니다.
말은 '칸'에서 다른 '칸'으로 움직이는데, '칸'을 잇는 단방향 간선을 통해서만 움직일 수 있습니다.
게임은 훈이가 항상 먼저 시작합니다.
만약 두 게임 모두에서 말을 움직일 수 없다면, 해당 플레이어는 집니다.

훈이는 말이 놓이는 초기 상황이 주어지고, 이 상황에서 서로가 항상 최적의 플레이를 한다고 가정하면, 누가 이길지 궁금해 합니다. 훈이에게 누가 이길지 알려주세요!

입력:
프로그램 입력은 두 개의 게임 판에 대한 설명으로 시작합니다.
각 게임판의 정보는 '칸'의 개수 N과 '칸'을 잇는 간선의 개수 M (1 <= N, M <= 100000)으로 시작합니다.
이후 M개의 줄에 A번 칸에서 B번 칸으로 이어지는 간선의 정보가 a b의 형식으로 들어옵니다.
각 칸들은 숫자로 1번부터 N번까지 매겨져 있습니다.

게임판에 대한 입력이 끝난 후, 훈이가 궁금해하는 초기 상황이 몇 개나 되는지에 대한 숫자 Q가 들어옵니다. (1 <= Q <= 100000)

이후, Q개의 줄마다 X Y의 형식으로 말이 놓여지는 초기 상황이 들어옵니다.
이는 첫번째 게임의 말이 X번째 칸에, 두번째 게임의 말이 Y번째 칸에 있음을 의미합니다.


출력:
훈이가 궁금해하는 초기 상황이 X Y의 형식으로 주어질 때마다, 훈이가 이긴다면 'W'를, 짱구가 이긴다면 'P'를 줄을 바꿔서 출력해주세요.

댓글을 작성하려면 로그인해야 합니다.