CF187C Weak Memory

Zart PMP is qualified for ICPC World Finals in Harbin, China. After team excursion to Sun Island Park for snow sculpture art exposition, PMP should get back to buses before they leave. But the park is really big and he does not know how to find them. The park has $ n $ intersections numbered $ 1 $ through $ n $ . There are $ m $ bidirectional roads that connect some pairs of these intersections. At $ k $ intersections, ICPC volunteers are helping the teams and showing them the way to their destinations. Locations of volunteers are fixed and distinct. When PMP asks a volunteer the way to bus station, he/she can tell him the whole path. But the park is fully covered with ice and snow and everywhere looks almost the same. So PMP can only memorize at most $ q $ intersections after each question (excluding the intersection they are currently standing). He always tells volunteers about his weak memory and if there is no direct path of length (in number of roads) at most $ q $ that leads to bus station, the volunteer will guide PMP to another volunteer (who is at most $ q $ intersections away, of course). ICPC volunteers know the area very well and always tell PMP the best way. So if there exists a way to bus stations, PMP will definitely find it. PMP's initial location is intersection $ s $ and the buses are at intersection $ t $ . There will always be a volunteer at intersection $ s $ . Your job is to find out the minimum $ q $ which guarantees that PMP can find the buses.

N/A

N/A

The first sample is illustrated below. Blue intersections are where volunteers are located. If PMP goes in the path of dashed line, it can reach the buses with $ q=3 $ : In the second sample, PMP uses intersection 6 as an intermediate intersection, thus the answer is 3.