Catch the Bomb
Time limit2sMemory limit128 MB
Given forbidden left and upper neighbor pairs over 26 letters, find the largest fillable square grid, capped at 20.
- Level
Medium7 of 10
- Topics
- Graph, Topological sort, Dynamic programming
- Solved
- No attempts yet
Problem
Seunghyeok, a mad scientist, wants to prank Mungi with a bomb disguised as a present. He builds a square grid and puts one easily detonated element into every cell. The same element may go into as many cells as he likes.
Each kind of element is written as a single lowercase letter, so at most 26 kinds are available.
The order the elements sit in is what causes trouble. Some rules say that element and element blow up violently the moment sits immediately to the left of or immediately above . The present has to survive until Mungi opens it, so Seunghyeok must fill the grid without a single such placement.
Mungi likes a bigger present, but he will not take anything that is not a square. Find the largest side length of a square grid that can be filled under these rules. A 1 × 1 grid has no adjacent cells, so it can always be built.
Input
The first line contains the number of test cases .
The first line of each test case contains the number of explosion rules (). Each of the next lines holds one rule as two lowercase letters , meaning an explosion happens when is immediately to the left of or immediately above . The two letters may be the same.
Output
For each test case, print the largest possible side length on its own line. If a grid with side length 20 or more can be built, print 20.