Polish version    English version  
  Reprezentacja -> Relacje z olimpiad


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
Lista reprezentantów
Osiągnięcia
Relacje z olimpiad
BOI 1999
CEOI 1998
CEOI 1997
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
Ten dokument nie jest dostępny w polskiej wersji językowej.


Problem: SHO

Shooting Contest

Welcome to the Annual Byteland Shooting Contest. Each competitor will shoot to a target which is a rectangular grid. The target consists of r*c squares located in r rows and c columns. The squares are coloured white or black. There are exactly two white squares and r-2 black squares in each column. Rows are consecutively labelled 1,..,r from top to bottom and columns are labelled 1,..,c from left to right. The shooter has c shots.

A volley of c shots is correct if exactly one white square is hit in each column and there is no row without white square being hit. Help the shooter to find a correct volley of hits if such a volley exists.

Example

Consider the following target:

Volley of hits at white squares in rows 2, 3, 1, 4 in consecutive columns 1, 2, 3, 4 is correct.

Task

Write a program that:

  • reads the number of data blocks from the text file SHO.IN; each block contains a complete set of data for the problem;
  • for each block
  • reads the target size and the layout of white squares;
  • verifies whether any correct volley of hits exists and if so, finds one of them;
  • writes the result to the text file SHO.OUT;

Input

The first line of the input file SHO.IN contains the number of data blocks x, 1 <= x <= 5. The following lines constitute x blocks. The first block starts in the second line of the input file; each next block starts directly after the previous one.

The first line of each block contains two integers r and c separated by a single space, 2 <= r <= c <= 1000. These are the numbers of rows and columns, respectively. Each of the next c lines in the block contains two integers separated by a single space. The integers in the input line i + 1 in the block, 1 <= i <= c, are labels of rows with white squares in the i-th column.

Output

For the i-th block, 1 <= i <= x, your program should write to the i-th line of the file SHO.OUT either a sequence of c row labels (separated by single spaces) forming a correct volley of hits at white squares in consecutive columns 1, 2, ..., c, or one word NO if such a volley does not exists.

Example

For the text file SHO.IN:

2
4 4
2 4
3 4
1 3
1 4
5 5
1 5
2 4
3 4
2 4
2 3
one of the correct solutions is the text file SHO.OUT:
2 3 1 4
NO




Wersja do druku