2 人解决，2 人已尝试。
2 份提交通过，共有 18 份提交。
8.5 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
Because of the latest mishaps of their agents, Central Intelligence Agency of Byteland resolved to improve their activity. So far the biggest trouble has been a preparation of safe meetings of agents. Your program has to help in solving this. For a given description of the net of roads in Byteland and the initial positions of two agents, it should answer if their safe meeting is possible.
To consider a meeting safe the agents must hold to the following precautions:
the agents move during the day and the meetings take place at evening,
an agent must change his place of stay each day,
the agents can travel only along the roads connecting cities (unfortunately another encuberance is that in Byteland, there are one-way roads),
an agent cannot move too fast (it could look very suspicious) - during one day he cannot travel farther than to a neighbouring city),
the distance between two connected cities is so short, that an agent setting off from one city in the morning will reach another one before evening,
a meeting is said to be done if two agents are in the same city at the same evening.
Task
Write a program that:
1.reads the number of cities and the description of the net of roads in Byteland and the starting positions of agents,
2.checks if there is a safe meeting, and if so, then how many days it takes to arrange it,
3.writes the result.
In the first line , there are two integers n and m separated by a single space, where 1<=n<=250, 0<=m<=n*(n-1).
In the second line there are two integers a1 and a2 separated by a single space, 1<=a1, a2<=n and a1<>a2, denoting respectively the starting positions of agents No 1 and No 2.
In the m following lines there are pairs of natural numbers a and b separated by single spaces, 1<=a,b<=n and a<>b, denoting that there is a road from city a to city b.
There should be exactly one line and it should contain:
1.exactly one positive integer which is the minimal time (in days) needed to arrange a safe meeting of two agents - if such meeting is possible,
2.a word NIE (which is NO in Polish) - if such meeting is not possible.
6 7 1 5 1 2 4 5 2 3 3 4 4 1 5 4 5 6
3
2 人解决，2 人已尝试。
2 份提交通过，共有 18 份提交。
8.5 EMB 奖励。