만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

홍수 난 바닥 고치기

면접 대비

시간 제한3초메모리 제한2048 MB

요약
2xn 격자에서 '#'은 막힌 칸, '.'은 빈 칸일 때, 빈 칸을 1x2 조각으로 채우는 방법이 하나인지, 여러 개인지, 없는지 판별합니다.
난이도

보통10점 중 5점

유형
동적 계획법, 구현
정답자
아직 제출이 없습니다

문제

아르키메데스는 부력에 관한 유명한 실험을 했다. 그런데 목욕을 하던 중 생각에 너무 몰두한 나머지, 물이 욕조 가장자리를 넘쳐 벽 근처 바닥을 적시는 순간을 알아차리지 못했다. 그 바람에 값비싼 마루(파케이)가 돌이킬 수 없이 손상되었다!

그래도 모든 것이 잃어버린 것은 아니었다. 손상되지 않은 마루 조각이 아직 여러 개 남아 있었다. 벽 근처의 마루는 길고 좁은 2×n2\times n 칸짜리 띠 모양이었다. 아르키메데스에게는 벽과 평행하게 또는 수직으로 놓을 수 있는 1×21\times 2 크기의 마루 조각이 무한히 있었다. 그는 조각을 자르고 싶지 않았다. 위대한 과학자답게, 그는 손상된 부분을 겹치지 않는 1×21\times 2 칸 조각으로 채우면 마루를 복원하는 방법이 정확히 하나뿐이라는 것을 계산해 냈다.

역사학자들이 아르키메데스의 계산을 검증하도록 도와라. 주어진 2×n2\times n 마루 배치에서, 손상된 칸을 1×21\times 2 조각으로 채우는 방법이 정확히 하나인지 판단하라. 아르키메데스가 틀렸다면, 복원 방법이 여러 개인지 아니면 방법이 아예 없는지 알아내라.

입력

첫 줄에 테스트 케이스의 수 TT (1≤T≤1041 \le T \le 10^4)가 주어진다. 이후 각 테스트 케이스가 이어진다.

각 테스트 케이스의 첫 줄에는 마루의 길이 nn (1≤n≤2⋅1051 \le n \le 2\cdot 10^5)이 주어진다. 다음 두 줄에는 각각 정확히 nn 글자로 마루의 상태가 주어진다. .은 손상된 칸, #은 손상되지 않은 칸을 뜻한다.

모든 테스트 케이스의 nn 합은 2⋅1052\cdot 10^5을 넘지 않는다.

출력

각 테스트 케이스마다 마루를 복원하는 방법이 정확히 하나이면 Unique, 여러 개이면 Multiple, 복원이 불가능하면 None을 출력한다.

예제1

  1. 예제 1

    입력
    4
    10
    #.......##
    ##..#.##..
    6
    ...#..
    ..#...
    8
    ........
    ........
    3
    ###
    ###
    
    예상 출력
    Unique
    None
    Multiple
    Unique