using System;

using System.Collections.Generic;   

using System.Linq;

using System.Diagnostics;

public class Program

{

    public static void Main()

    {

        var employees = new List<Employee>();

        var departments = new List<Department>();  

        Random rnd = new Random();

        for (var i = 0; i < 100000; i++)

        {           

            int departmentId  = rnd.Next(1, 4000);          

            employees.Add(new Employee() { Id = i, DepartmentId = departmentId });

            if (!departments.Any(d => d.Id == departmentId))

            {

                departments.Add(new Department() { Id = departmentId });

            }

        }       

        var stopwatch = Stopwatch.StartNew();

        var results = Run(employees, departments);

        stopwatch.Stop();

        if (results.Count() != 100000)

            throw new System.Exception("wrong answer");

        Console.WriteLine(stopwatch.ElapsedMilliseconds);

    }

    //This method takes about 4-5 seconds to run. The goal is to make it run in less than 50ms. RULES: ONLY CHANGE THIS METHOD, DON'T TOUCH SIGNATURE

    public static List<EmployeeDepartment> Run(IEnumerable<Employee> employees, IEnumerable<Department> departments)

    {

        var results = new List<EmployeeDepartment>();

        foreach (var employee in employees)

        {

            var res = new EmployeeDepartment()

            {

                Employee = employee,

                Department = departments.First(d=>d.Id == employee.DepartmentId)

            };

            results.Add(res);

        }

        return results;

    }

}

public class Employee

{

    public int Id {get;set;}

    public int DepartmentId {get;set;}

}

public class Department

{

    public int Id {get;set;}

    public string Name {get;set;}

}

public class EmployeeDepartment

{

    public Department Department {get;set;}

    public Employee Employee {get;set;}

}