You're playing Minecraft, and having fun exploring your world in Creative mode. Your world consists of Desert, Forest, and Taiga biomes.
You've explored some of the world, but not all of it. Thus, for some places, you know their biome, and for others, you don't. The world is given as a 2D top-down view, with some spaces ("chunks") unknown, and others with a known biome.
You especially like Taiga biomes. You've already explored at least one space that is a taiga biome, and you know that your world has exactly one taiga biome. Given this information, your task is to figure out the maximum amount of spaces (chunks) on the 2D world map that can be part of a taiga biome, and which spaces could potentially be part of the taiga biome.
Two spaces are considered part of the same biome if you can travel on the 2D grid from one space to the other, traveling on only spaces of the given biome. For example, if two spaces are both in Taiga biomes, but to travel from one to the other you are forced to cross a desert, they are not part of the same biome.
The input consists of 20 lines, each containing 20 characters: the 20 by 20 world map.
If a given space is part of a Taiga biome, it will be represented by a "T" in the input file.
If a given space is part of a Desert biome, it will be represented by a "D" in the input file.
If a given space is part of a Forest biome, it will be represented by an "F" in the input file.
If you haven't explored a certain space, it will be representing as a single dot (".") in the input file.
Output 20 lines: the given input, except if any unexplored spaces (chunks) could potentially be part of a Taiga biome, change their character to a "T".
## Input
The input consists of 20 lines, each containing 20 characters: the 20 by 20 world map.If a given space is part of a Taiga biome, it will be represented by a "T" in the input file.If a given space is part of a Desert biome, it will be represented by a "D" in the input file.If a given space is part of a Forest biome, it will be represented by an "F" in the input file.If you haven't explored a certain space, it will be representing as a single dot (".") in the input file.
## Output
Output 20 lines: the given input, except if any unexplored spaces (chunks) could potentially be part of a Taiga biome, change their character to a "T".
[samples]
**Definitions**
Let $ M \in \{D, F, T, .\}^{20 \times 20} $ be the 20×20 grid representing the world map, where:
- $ T $: known Taiga chunk,
- $ D $: known Desert chunk,
- $ F $: known Forest chunk,
- $ . $: unexplored chunk.
Let $ G = (V, E) $ be the 4-connected grid graph over $ M $, where each cell is a vertex, and edges connect horizontally/vertically adjacent cells.
Let $ T_{\text{known}} = \{ (i,j) \in [20] \times [20] \mid M[i][j] = T \} $ be the set of known Taiga chunks.
By assumption, $ T_{\text{known}} \neq \emptyset $.
Let $ C $ be the connected component in $ G $ containing $ T_{\text{known}} $, restricted to cells that are either $ T $ or $ . $.
**Constraints**
1. The world contains exactly one Taiga biome.
2. The Taiga biome is a single connected component in $ G $.
3. Only unexplored cells ($ . $) may be assigned to Taiga; known $ D $ and $ F $ are fixed and cannot be Taiga.
4. The Taiga biome must include all known $ T $ cells.
**Objective**
Identify the maximal set of unexplored cells ($ . $) that can be added to $ T_{\text{known}} $ to form a single connected component (the unique Taiga biome), such that:
- The resulting set is connected via 4-adjacency,
- No $ D $ or $ F $ cell is included,
- The set contains all known $ T $ cells.
Output the grid $ M' $, where:
- $ M'[i][j] = T $ if $ M[i][j] = T $ or ($ M[i][j] = . $ and $ (i,j) \in C $),
- $ M'[i][j] = M[i][j] $ otherwise.