Polish version    English version  
  History of OI -> V OI 1997/1998 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Schedule
Stats
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
V Olimpiada Informatyczna 1997/1998

Task: GON
Author: Adam Borowski
Chase

III stage contest  

Chase is a two-person board game. A board consists of squares numbered from 1 to n. 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:

  • it contains no triangles, i.e. there are no three distinct squares such that each pair of them is adjacent,
  • each square can be reached by each player.

A game consists of many turns. In one turn each player makes a single move. Each turn is started by player A. We say that player A is caught by player B if both pieces stand on the same square. Decide, if for a given initial positions of pieces, player B can catch player A, independently of the moves of his opponent. If so, how many turns player B needs to catch player A if both play optimally (i.e. player A tries to run away as long as he can and player B tries to catch him as quickly as possible).

Example
[Example]

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 A and B stand on the squares 9 and 4 respectively, then player B can catch player A in the third turn (if both players move optimally). If game starts with pieces on the squares 8 (player A) and 4 (player B) then player B cannot catch player A (if A plays correctly).

Task

Write a program that:

  • reads from the text file GON.IN the description of a board and numbers of squares on which pieces are placed initially.
  • decides if player B can catch player A and if so, computes how many turns he needs (we assume that both players play optimally);
  • writes the result to the text file GON.OUT.

    Input

    In the first line of the input file GON.IN there are four integers n, m, a and b separated by single spaces, where 2<=n<=3000, n-1<=m<=15000, 1<=a,b<=n and a <b. 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 A is placed, the number of the square on which the piece of player B 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.

    Output

    In the first and only line of the file GON.OUT there should be:

  • one word NIE (which means NO in Polish), if player B can not catch player A, or
  • one integer - the number of turns needed by B to catch A (if B can catch A).

    Example

    For the input file GON.IN:

    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 answer is the output file GON.OUT:
    3




  • Print friendly version