In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Chase is a two-person board game, we call the players and . A board consists of squares numbered from to . For each pair of different squares it is known if they are adjacent to one another or they are not. Each player has a piece at his disposal. At the beginning of a game pieces of players are placed on fixed, distinct squares. In one turn a player can leave his piece on the square it stands or move it to an adjacent square.
A game board has the following properties:
A game consists of many turns. In one turn each player makes a single move. Each turn is started by player .
We say that player is caught by player if both pieces stand on the same square. Decide, if for a given initial positions of pieces, player can catch player , independently of the moves of his opponent. If so, how many turns player needs to catch player if both play optimally (i.e. player tries to run away as long as he can and player tries to catch him as quickly as possible).
Consider the board in the figure. Adjacent squares (denoted by circles) are connected by edges. If at the beginning of a game pieces of players and stand on the squares and respectively, then player can catch player in the third turn (if both players move optimally). If game starts with pieces on the squares (player ) and (player ) then player cannot catch player (if plays correctly).
Write a program that:
In the first line of the standard input there are four integers , , and separated by single spaces, where , , and . These are (respectively): the number of squares of the board, the number of adjacent (unordered) pairs, the number of the square on which the piece of player is placed, the number of the square on which the piece of player is placed.
In each of the following lines there are two distinct positive integers separated by a single space, which donote numbers of adjacent squares.
In the first and only line of the standard output there should be:
For the input data:
9 11 9 4 1 2 3 2 1 4 4 7 7 5 5 1 6 9 8 5 9 8 5 3 4 8
the correct result is:
Task author: Adam Borowski.