using System;

using System.Collections.Generic;

public class Program

{

    /* Animal Shelter: An animal shelter, which holds only dogs and cats, operates on a strictly"first in, first

    out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter,

    or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of

    that type). They cannot select which specific animal they would like. Create the data structures to

    maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog,

    and dequeueCat. You may use the built-in Linkedlist data structure.*/

    public abstract class Animal {

        public int Id;

    }

    public class Dog: Animal{}

    public class Cat: Animal{}

    public class AnimalShelter{

        private int nextId;

        private Queue<Dog> dogs;

        private Queue<Cat> cats;

        public AnimalShelter(){

            this.nextId = 1;

            dogs = new Queue<Dog>();

            cats = new Queue<Cat>();

        }

        public void Enqueue(Animal animal){

            if (animal == null) return;

            animal.Id = nextId;

            nextId++;

            if (animal is Dog){

                dogs.Enqueue(animal as Dog);

            }

            else cats.Enqueue(animal as Cat);

        }

        public Animal DequeueAny(){

            if (dogs.Count == 0 && cats.Count == 0) return null;

            var oldestDogId = dogs.Count == 0 ? int.MaxValue : dogs.Peek().Id;

            var oldestCatId = cats.Count == 0 ? int.MaxValue : cats.Peek().Id;

            if (oldestDogId < oldestCatId){

                return dogs.Dequeue();

            }

            else return cats.Dequeue();

        }

        public Dog DequeueDog(){

            return dogs.Count == 0 ? null : dogs.Dequeue();

        }

        public Cat DequeueCat(){

            return cats.Count == 0 ? null : cats.Dequeue();

        }

    }

    public static void Main()

    {

        var shelter = new AnimalShelter();

        Console.WriteLine("Hello World");

    }

}