Company: Albertsons_21_feb
Difficulty: medium
The Message Delivery Alex works at a company of N people, numbered 1 to N . Alex is person 1 and Sam is person N . Alex wants a message to reach Sam. A message can only be handed from one person to another when the two know each other, so it travels along a chain: Alex hands it to a colleague, that colleague hands it on, and so forth until it arrives at Sam. Knowing each other is mutual, so the message can move in either direction along a link. Find a chain that puts the message in Sam's hands after as few hand-offs as possible. Input Format The first line contains two space-separated integers N and M — the number of people and the number of acquaintance links. Each of the next M lines contains two space-separated integers a and b , meaning person a and person b know each other. The relation is mutual, and the two endpoints may be written in either order. Output Format If no chain of acquaintances leads from Alex to Sam, print the single word IMPOSSIBLE . Otherwise print two lines: the