Eight railway stations A, B, C, D, E, F, G and H are connected either by two- way passages or one- way passages. One- way passages are from C to A, E to G, B to F, D to H, G to C, E to C and H to G. Two- way passages are between A and E, G and B, F and D, and E and D. In how many different ways can a train travel from F to A without passing through any station more than once?

To find the number of different ways a train can travel from F to A without passing through any station more than once, we need to trace all possible paths. First, let's list the direct connections from each station that can be used to move forward: One-way passages (X -> Y): C -> A E -> G B -> F (This means B can go to F, but F cannot go to B) D -> H G -> C E -> C H -> G Two-way passages (X Y): A E (A -> E and E -> A) G B (G -> B and B -> G) F D (F -> D and D -> F) E D (E -> D and D -> E) Now, let's list all possible outgoing routes from each station relevant to reaching A: From A: E From B: F, G From C: A From D: H, F, E From E: G, C, A, D From F: D From G: C, B From H: G We start at F and want to reach A. 1. From F, the only immediate destination is D (via F D). Path starts: F -> D 2. From D, we have three options: H, E, or F. F is already visited, so we can go to H or E. Option 2a: F -> D -> H From H, the only destination is G (via D -> H). Path continues: F -> D -> H -> G From G, we have two options: C or B. If we go to B, B only leads to F (which is visited) or G (which is visited). So B is a dead end for reaching A without repetition. Thus, we must go to C. Path continues: F -> D -> H -> G -> C From C, the only destination is A (via C -> A). Path 1: F -> D -> H -> G -> C -> A (All stations unique) Option 2b: F -> D -> E From E, we have three options without repeating D: G, C, or A. Option 2b.i: F -> D -> E -> G From G, as before, B is a dead end. So we go to C. Path continues: F -> D -> E -> G -> C From C, we go to A. Path 2: F -> D -> E -> G -> C -> A (All stations unique) Option 2b.ii: F -> D -> E -> C From C, we go to A. Path 3: F -> D -> E -> C -> A (All stations unique) Option 2b.iii: F -> D -> E -> A This directly reaches A. Path 4: F -> D -> E -> A (All stations unique) We have found 4 distinct paths from F to A without passing through any station more than once: 1. F -> D -> H -> G -> C -> A 2. F -> D -> E -> G -> C -> A 3. F -> D -> E -> C -> A 4. F -> D -> E -> A Therefore, there are 4 different ways. The final answer is D