class DoubleLinkedList{
    private Node head;
    private Node tail;
    private int size;

    public DoubleLinkedList(){
        head=new Node(0,0);
        tail=new Node(0,0);
        head.next=tail;
        tail.pre=head;
        size=0;
    }

    public void addFirst(Node node){
        node.next=head.next;
        node.pre=head;
        head.next.pre=node;
        head.next=node;
        size++;
    }

    public void remove(Node node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
        size--;
    }

    public Node removeLast(){
        if(tail.pre==head){
            return null;
        }
        Node last=tail.pre;
        remove(last);
        return last;
    }

    public int size(){
        return size;
    }

    public static class Node{
        int key;
        int value;
        Node pre;
        Node next;
        public Node(int key,int value){
            this.key=key;
            this.value=value;
        }
    }
}