In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

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.

Write a program which:

- reads the number of cities and the description of the net of roads in Byteland and the starting positions of agents from the standard input,
- checks if there is a safe meeting, and if so, then how many days it takes to arrange it,
- writes the result to the standard output.

In the first line of the standard input, there are two integers and separated by a single space, where , .

In the second line there are two integers and separated by a single space, , and , denoting respectively the starting positions of agents No 1 and No 2.

In the following lines there are pairs of natural numbers and separated by single spaces, and , denoting that there is a road from city to city .

There should be exactly one line in the standard input and it should contain:

- 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,
- a word
`NIE`(which is NO in Polish) - if such meeting is not possible.

For the input data:

6 7 1 5 1 2 4 5 2 3 3 4 4 1 5 4 5 6

the correct result is:

3

*Task author: Tomasz Walen.*