문제

한국정보기술진흥원은 한때는 찬란한 문명을 이룩했던 거대한 국가였습니다. 오랜 세월이 지난 지금, 찬란했던 과거의 발자취들은 고대 유적 안에 남아 탐험가들에게 발견되기를 기다리고 있습니다.

진흥이는 이 고대 유적을 탐사하여 한국정보기술진흥원의 유물을 발굴하고자 합니다.

진흥이가 탐사하고자 하는 고대 유적은 개의 방으로 이루어져 있으며, 총 개의 복도가 각각 서로 다른 두 방을 잇고 있습니다. 번째 복도는 번 방과 번 방을 양방향으로 연결하고 있습니다. 번 방은 유적의 입구와 연결되어 있어, 진흥이가 탐사를 시작한 순간 진흥이는 번 방에 위치해 있습니다.

한국정보기술진흥원은 뛰어난 기술력을 보유하고 있었습니다. 만들어진 이후 수천 년이 지난 지금도, 침입자를 감시하기 위한 기계 감시자들이 각 방을 감시하고 있습니다. 번 방의 감시자는 진흥이가 탐사를 시작하기 초 전부터 가동을 시작하여, 초 동안 냉각을 진행한 뒤, 초 동안 번 방을 감시하는 과정을 반복합니다. 가 이라면 감시자는 냉각 없이 항상 방을 감시하며, 가 이라면 감시자는 감시 없이 항상 냉각을 진행합니다. 만약 진흥이가 감시가 진행 중인 방에 들어간다면 고대 유적은 자동으로 모든 유물을 소각할 것이기 때문에, 진흥이는 항상 감시자가 냉각 중인 방에만 들어갈 수 있습니다. 임이 알려져 있습니다. 즉, 진흥이가 탐사를 시작한 순간 번 방의 감시자는 냉각 중입니다.

진흥이는 초부터 시작하여, 각 정수 에 대해서 정확히 초에 두 가지 행동 중 하나를 선택할 수 있습니다.

1. 초 동안 자신이 있던 방에 가만히 있기. 진흥이가 방에 있는 동안 감시자가 냉각을 끝내고 감시에 돌입하면, 진흥이가 포착될 수 있음에 주의해야 합니다.
2. 초 동안 자신이 있던 방과 복도로 연결된 다른 방에 이동하기. 진흥이는 정확히 초에 복도로 진입하여, 정확히 초에 반대쪽 방에 도착합니다. 진흥이가 복도를 통해 이동하는 동안에는 그 어떠한 감시자도 진흥이를 포착할 수 없습니다. 그러나 진흥이가 이동하여 도착한 방의 감시자가 해당 방을 감시 중이라면, 역시 진흥이가 포착될 수 있음에 주의해야 합니다.

진흥이는 각 방에 대해서, 그 방에 도달할 수 있는지의 여부와, 가능하다면 그 방에 도달하기 위해 필요한 최소한의 초 단위 시간을 구하고 싶습니다. 에 대해서, 진흥이가 번 방에 도달할 수 있는지의 여부와, 가능하다면 최소 시간을 구해 주세요.

입력

첫 번째 줄에 두 정수 이 주어집니다.

이후 개의 줄 각각에는 감시자의 행동 정보를 나타내는 두 음이 아닌 정수 가 공백으로 구분되어 주어집니다.

이후 개의 줄 각각에는 각 복도가 연결하는 방의 정보를 나타내는 서로 다른 두 정수 가 공백으로 구분되어 주어집니다.

출력

첫 번째 줄에 총 개의 정수를 공백으로 구분하여 출력합니다. 이중 번째 정수는 진흥이가 번 방에 도달하기 위해 필요한 최소한의 시간이어야 합니다. 만약 진흥이가 번 방에 도달하는 것이 불가능하다면, 번째 정수는 이어야 합니다.

노트

• 에 대해,