class Position{
     int x;
     int y;
     public Position(int x, int y){
         this.x = x;
         this.y = y;
     }
     public boolean isEqual(Position p){
         return (p.x == this.x && p.y == this.y);
     }
    }
public class SnakeGame {

    /** Initialize your data structure here.
        @param width - screen width
        @param height - screen height 
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
    int width;
    int height;
    int[][] food;
    int len;
    LinkedList<Position> snake;
    int score;
    public SnakeGame(int width, int height, int[][] food) {
         this.width = width;
        this.height = height;
        this.food = food;
        snake = new LinkedList<Position>();
        snake.add(new Position(0,0));
        len = 0;
    }
    
    /** Moves the snake.
        @param direction - ‘U‘ = Up, ‘L‘ = Left, ‘R‘ = Right, ‘D‘ = Down 
        @return The game‘s score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body. */
    public int move(String direction) {
        Position cur = new Position(snake.get(0).x , snake.get(0).y);  // current position is the head of snack;
        if(direction.equals("R")) cur.y++;
        if(direction.equals("L")) cur.y--;
        if(direction.equals("U")) cur.x--;
        if(direction.equals("D")) cur.x++;
        
        if(!isValid(cur))
            return -1;

        //case 1 eat food
        if(len < food.length && cur.isEqual(new Position(food[len][0], food[len][1]))){
            snake.addFirst(cur);
            len ++;
        }
        else{  // just add head and remove the tail
            snake.addFirst(cur);
            snake.removeLast();
        }
        return len;
    }
    public boolean isValid(Position cur){
        //System.out.print(" x " + cur.x + " y " + cur.y + "  height " + height + " width "+ width );
        if(cur.x < 0 || cur.x >= height || cur.y < 0 || cur.y >= width){ // the snack meet the boundry;
            return false;
        }
            
        for(int i = 1; i < snake.size() -1; i++){  
            // the snack bit itself; !!!! 不用考虑head和tail  new head is legal to be in old tail‘s position, remove from set temporarily 
            Position next = snake.get(i);
            if(next.isEqual(cur)){
                return false;
            }
        }
        return true;
    }
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);
 */