Connect

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1148		Accepted: 375

Description

Figure 1	Figure 2	Figure 3a	Figure 3b	Figure 4

Your task is to decide if a specified sequence of moves in the board game Twixt ends with a winning move.

In this version of the game, different board sizes may be specified. Pegs are placed on a board at integer coordinates in the range [0, N]. Players Black and White use pegs of their own colZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vci4gQmxhY2sgYWx3YXlzIHN0YXJ0cyBhbmQgdGhlbiBhbHRlcm5hdGVzIHdpdGggV2hpdGUsIHBsYWNpbmcgYSBwZWcKIGF0IG9uZSB1bm9jY3VwaWVkIHBvc2l0aW9uICh4LHkpLiBCbGFjaw=="s endzones are where x equals 0 or N, and White's endzones are where y equals 0 or N. Neither player may place a peg in the other player's endzones. After each play the latest position is connected by a segment to every position with a peg of the same color that is a chess knight's move away (2 away in one coordinate and 1 away in the other), provided that a new segment will touch no segment already added, except at an endpoint. Play stops after a winning move, which is when a player's segments complete a connected path between the player's endzones.

For example Figure 1 shows a board with N=4 after the moves (0,2), (2,4), and (4,2). Figure 2 adds the next move (3,2). Figure 3a shows a poor next move of Black to (2,3). Figure 3b shows an alternate move for Black to (2,1) which would win the game.

Figure 4 shows the board with N=7 after Black wins in 11 moves:
(0, 3), (6, 5), (3, 2), (5, 7), (7, 2), (4, 4), (5, 3), (5, 2), (4, 5), (4, 0), (2, 4).

Input

The input contains from 1 to 20 datasets followed by a line containing only two zeroes, "0 0". The first line of each dataset contains the maximum coordinate N and the number of total moves M where 3 < N < 21, 4 < M < 250, and M is odd. The rest of the dataset contains a total of M coordinate pairs, with one or more pairs per line. All numbers on a line will be separated by a space. M being odd means that Black will always be the last player. All data will be legal. There will never be a winning move before the last move.

Output

The output contains one line for each data set: "yes" if the last move is a winning move and "no" otherwise.

Sample Input

4 5
0 2 2 4 4 2 3 2 2 3
4 5
0 2 2 4 4 2 3 2 2 1
7 11
0 3 6 5 3 2 5 7 7 2 4 4
5 3 5 2 4 5 4 0 2 4
0 0

Sample Output

no
yes
yes

Source

Mid-Central USA 2005

黑白棋的游戏，在n*n的棋盘上，黑棋先手，且最后一步是黑棋。当黑棋从x=0连接的到x=n，时黑棋获胜，问最后一步是不是致胜的一步

每个点都可以和它周围的八个点连接，类似象棋中的马，但是在连接两个点的时候，在连线之间不能有其他的连线（包括黑棋自身的连线）。所以在连接一条线的时候，要判断其他的可能会切割这条线的九条线是否存在。

先判断不包含最后一步的黑棋能不能胜利，再判断加上最后一步后能不能获胜，如果开始不能获胜，后来获胜，那么输出yes，否则，输出no

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std ; int vis[500] ; int Map[25][25] , c[500][500] ;//????1??°×??-1 queue 
      
        que ; void solve1(int i,int j,int n,int temp) { if( (i-1) >= 0 && (i+1) < n && (j-1) >= 0 && c[ (i-1)*n+j ][ (i+1)*n+(j-1) ] != 0 ) return ; if( (i-1) >= 0 && (j-2) >= 0 && (i+1) < n && (j-1) >= 0 && c[ (i-1)*n+(j-2) ][ (i+1)*n+(j-1) ] != 0 ) return ; if( (j-3) >= 0 && (i+1) < n && (j-1) >= 0 && c[ i*n+(j-3) ][ (i+1)*n+(j-1) ] != 0 ) return ; if( (j-1) >= 0 && (i+1) < n && (j+1) < n && c[ i*n+(j-1) ][ (i+1)*n+(j+1) ] != 0 ) return ; if( (j-1) >= 0 && (i+2) < n && c[ i*n+(j-1) ][ (i+2)*n+j ] != 0 ) return ; if( (j-1) >= 0 && (i+2) < n && (j-2) >= 0 && c[ i*n+(j-1) ][ (i+2)*n+(j-2) ] != 0 ) return ; if( (i-1) >= 0 && (j-1) >= 0 && (i+1) < n && c[ (i-1)*n+(j-1) ][ (i+1)*n+j ] != 0 ) return ; if( (i+1) < n && (j-2) >= 0 && c[ (i+1)*n+j ][ i*n+(j-2) ] != 0 ) return ; if( (j-2) >= 0 && (i+2) < n && (j-1) >= 0 && c[ i*n+(j-2) ][ (i+2)*n+(j-1) ] != 0 ) return ; c[ i*n+j ][ (i+1)*n+(j-2) ] = c[ (i+1)*n+(j-2) ][ i*n+j ] = temp ; return ; } void solve2(int u,int v,int n,int temp) { if( (u-1) >= 0 && (v-1) >= 0 ) { if( (u+1) < n && c[ (u-1)*n+(v-1) ][ (u+1)*n+v ] != 0 ) return ; if( (u+1) < n && (v-2) >= 0 && c[ (u-1)*n+(v-1) ][ (u+1)*n+(v-2) ] != 0 ) return ; if( (v-3) >= 0 && c[ (u-1)*n+(v-1) ][ u*n+(v-3) ] != 0 ) return ; } if( (v-1) >= 0 ) { if( (u-1) >= 0 && (v+1) < n && c[ u*n+(v-1) ][ (u-1)*n+(v+1) ] != 0 ) return ; if( (u-2) >= 0 && c[ u*n+(v-1) ][ (u-2)*n+v ] != 0 ) return ; if( (u-2) >= 0 && (v-2) >= 0 && c[ u*n+(v-1) ][ (u-2)*n+(v-2) ] != 0 ) return ; } if( (u+1) < n && (v-1) >= 0 && (u-1) >= 0 && c[ (u+1)*n+(v-1) ][ (u-1)*n+v ] != 0 ) return ; if( (u-1) >= 0 && (v-2) >= 0