Data structures / trees

Please use C language only

Tom and Jerry are in the same house, which has n rooms with n two-way hallways betweencthem. Tom is trying to catch Jerry , and the only way he can catch him is if they are both in the same room or if they encounter each other on the way.

They can move between adjacent rooms or stay in the same place. Jerry has a deep understanding of Toms behavior patterns, so he can accurately predict where Tom will go next. They start and end the move at the same time. If both of them are very clever, please determine whether Tom can catch Jerry.

I will leave an example and some pictures related to question

these are the rules for input and output for the program:

1)the program needs to read its input from a textfile: say "input.txt" and print its output in another textfile say "output.txt"

the pictures explain how the inputs work and also a sample input and output taken from files

Example 1: Tom starts at room 2, while Jerry starts at room 1 . Jerry knows which way Tom will move around the triangle, and he can simply always move in the same way to avoid Tom forever. Example 2: Tom starts at room 1, while Jerry starts at room 4. Tom can go to room 4 on his first move and win, since Jerry must either go to room 1 (then he meets Tom on the hallway from 1 to 4) or stay at room 4 (then he meets Tom at room 4). So there is no strategy for Jerry to win. Input The first line of input gives the number of test cases, T(1T50). Then T test cases follow each described in the following way: 1. The first line contains three integers n,t,j(3n2105;1t,jn) separated by spaces, which indicate the number of rooms and the starting rooms of Tom and Jerry. 2. In the subsequent n lines, pairs of integers u and v(1u,vn,u=v) denote the existence of a two-way hallway linking rooms u and v. note: The rooms are connected and there is at most one hallway between two rooms. Output For each input produce one line of output. Print 1 if Jerry can escape Tom forever and 0 otherwise. Sample Input 6 321 21 32 13 414 14 12 13 23 412 12 23 24 34 711 41 21 53 46 42 75 34 853 83 51 26 68 12 Sample Output 1 0 1 0 0 1