This page is still under construction.

Parts of this page are still being built. What you see may change.

Cube

Time limit1sMemory limit128 MB

Summary
Given an n by n by n grid of letters, decide whether the connected same-letter pieces can be pulled apart without cutting, meaning no single piece separates the cube.
Level

Hard8 of 10

Topics
Graph, DFS, Geometry, Implementation
Solved
No attempts yet

Problem

Imagine a large cube built from solid, interlocking pieces of various shapes. If the pieces are entangled enough, the only way to pull them apart might be to cut some of them. We can ask: "is the cube stable?" That is, is it physically impossible to separate the cube into 22 or more fragments without deforming or cutting any individual piece?

Your program must answer this question for several such cubes.

The pieces that make up a cube are specified as follows: divide the cube into a grid of n×n×nn \times n \times n miniature cubes, each labeled with a capital letter. Two adjacent (face-sharing) minicubes are joined together if and only if they carry the same letter. For example, the cube in the first test case consists of 33 solid pieces.

Input

Your program is given the specification of up to 1010 different cubes. The first two lines of each specification are the size of the cube, nn (1≤n≤10)(1 \le n \le 10), and a blank line. The remaining n×(n+1)n \times (n + 1) lines describe the nn horizontal layers of the cube from bottom to top. Each layer specification is an n×nn \times n square giving the label of every minicube on that layer, followed by a blank line. There are no spaces in the input. The input is terminated by the number 00 on a line by itself.

Output

For each cube, in the order given, print Yes if the cube is stable and No if it is not.

Examples5

  1. Example 1

    Input
    2
    
    AB
    AB
    
    BB
    BA
    
    3
    
    AAA
    BBB
    AAA
    
    AAA
    ABA
    AAA
    
    ABA
    ABA
    ABA
    
    0
    
    Expected output
    No
    Yes
    
  2. Example 2

    Input
    1
    
    A
    
    0
    
    Expected output
    Yes
    
  3. Example 3

    Input
    3
    
    AAA
    BBB
    AAA
    
    AAA
    ABA
    AAA
    
    ABA
    ABA
    ABA
    
    0
    
    Expected output
    Yes
    
  4. Example 4

    Input
    1
    
    A
    
    2
    
    AB
    AB
    
    BB
    BA
    
    0
    
    Expected output
    Yes
    No
    
  5. Example 5

    Input
    3
    
    AAA
    BBB
    AAA
    
    AAA
    ABA
    AAA
    
    ABA
    ABA
    ABA
    
    1
    
    Q
    
    2
    
    AA
    AA
    
    BB
    BB
    
    0
    
    Expected output
    Yes
    Yes
    No