DungeonBuilder

Your randomized map builder has spit out the dungeon layout for your new computer-based role playing game. The map is complex, with each room leading to at most 8 other rooms. Each path out of a room is given a number, so the player can simply hit a digit (1-8) on the keyboard to select his path. The builder also picked one room to be the starting location, and a group of the rooms to be winning positions (this group may be empty). A player will traverse the dungeon making a sequence of moves (digit selections). When done he will click 'Finish'. If the final room happens to be one of the winning positions, the player wins. Otherwise, the player loses. In addition, if a player tries to take a nonexistent path out of a room, he immediately loses.

The first 20 or so maps you built were excellent, but after a while you realized that the builder was somewhat predictable. Something had to be done, but you didn't want to recode the entire program. You decided to let the builder create a map M. Then you would generate a random number R between 1 and 7 inclusive. Using R and M you would construct a new map N. A sequence of moves wins in N if and only if the same sequence used in M would result in the player winning and cause the player to enter winning positions exactly R times. If you repeatedly enter the same winning position, each time contributes to the total. If the starting location is a winning position, the number of winning positions entered will be 1 prior to the first move of the sequence.

Given the map M and the number R, return the size, in number of rooms, of the smallest map equivalent to N. Two maps are equivalent if and only if every sequence of moves will produce the same outcome in both maps. In other words, two maps are different if and only if there exists some sequence of moves that will win on one map and lose on the other. A winning sequence of moves in a map K must begin at the starting location of K and end at one of the winning positions of K.

Element i of M will describe the paths leaving room i. It will contain precisely 8 terms separated by single spaces. Each term will either be X or some number j. If the kth number of element i of M is j, then the kth path out of room i leads to room j. X denotes no path exists corresponding to that number. For example, if

	M = { "0 0 1 1 X X X X",
              "2 1 0 0 X X X 2",
              "X X X X X X X X" },

then from room 0, paths 1 and 2 lead back to room 0. Paths 3 and 4 in room 0 lead to room 1. In room 1, paths 1 and 8 lead to room 2, paths 3 and 4 lead to room 0, and path 1 leads back to room 1. No paths lead out of room 2. Note that the paths are not bidirectional. start will say which room is the starting position, and finish will contain the winning positions. If the resulting map N is unwinnable, return 1.