using System;

​

public class Program

{

    static

        bool IsGroupSeparable(bool[,] peopleRelations, int N)

        {

            //peopleRelations = (bool[,])peopleRelations.Clone(); // Not required for the solution but avoids modifying the input

​

            var seatMap = new byte[N]; byte anySide = 0; byte leftSide = 1; byte rightSide = 2;

            int nbSeated = 0;

            bool trySeatAllAcquintances(int firstFellow)

            {

                int[] stackFellowsToCheck = new int[N]; int iStack = -1;

                stackFellowsToCheck[++iStack] = firstFellow;

​

                while (iStack > -1)

                {

                    int fellow = stackFellowsToCheck[iStack--];

                    byte sideForFriendsOfFriend = seatMap[fellow];

                    byte requiredSideForDirectFriends = sideForFriendsOfFriend == leftSide ? rightSide : leftSide;

                    for (int friend = firstFellow; friend < N; friend++)

                    {

                        if (fellow == friend)

                            continue;

                        if (peopleRelations[fellow, friend])

                        {

                            peopleRelations[fellow, friend] = peopleRelations[friend, fellow] = false;

                            var sideOfFriend = seatMap[friend];

                            if (sideOfFriend == anySide)

                            {

                                seatMap[friend] = requiredSideForDirectFriends;

                                nbSeated++;

                                stackFellowsToCheck[++iStack] = friend;

                            }

                            else

                            {

                                if (sideOfFriend != requiredSideForDirectFriends)

                                    return false;

                            }

                        }

                    }

                }

​

                return true;

            };

​

            int passenger;

            for (passenger = 0; passenger < N - 1; passenger++)

            {

                if (seatMap[passenger] != anySide)

                    continue;

                seatMap[passenger] = leftSide;

                nbSeated++;

                if (!trySeatAllAcquintances(passenger))

                    return false;

                if (nbSeated == N)

                    return true;

            }

            return true;

        }

    // Some testing material

    public static void Main()

    {

        Test(true, new bool[,]

        {  //A      B       C      D

            {false, true  , false, true }, // A

            {true , false , true , false}, // B

            {false, true  , false, true }, // C

            {true , false , true , false}, // D

        });

        Test(false, new bool[,]

        {

            {false, true  , false, true  , false},

            {true , false , false, false , false},

            {false, false , false, true  , true },

            {true , false , true , true  , true },

            {false, false , true , true  , false},

        });

        Test(true, new bool[,]

        {

            {false, true , false, true , false, false, false },

            {true , false, true , false, false, false, false },

            {false, true , false, true , false, true , false },

            {true , false, true , false, false, false, false },

            {false, false, false, false, false, false, true  },

            {false, false, true , false, false, false, true  },

            {false, false, false, false, true , true , false },

        });

        Test(true, new bool[,]

        {

            {false, false, true },

            {false, false, true },

            {true , true , false},

        });

​

        Test(true, new bool[,]

        {

            {false, false, true, false },

            {false, false, false, true },

            {true , false, false, true },

            {false, true , true, false },

        });

        Test(false, new bool[,]

        {

            {false, false, true, true  },

            {false, false, false, true },

            {true , false, false, true },

            {true , true , true , false},

        });

        int cycleLength = 1001; // Try putting 60000 ..

        Test(cycleLength % 2 == 0, GenLargestCycle(cycleLength));

        cycleLength++;

        Test(cycleLength % 2 == 0, GenLargestCycle(cycleLength));

    }

    static void Test(bool expectedResult, bool[,] peopleRelations) {

        int N = peopleRelations.GetLength(0);

        bool result = IsGroupSeparable(peopleRelations, N);

        Console.WriteLine("N = "+ N +" / Expected : "+expectedResult.ToString().PadRight(5)+" / Actual : "+ result.ToString().PadRight(5) + " / " + (expectedResult == result ? "PASS" : "FAIL"));

    }

    static bool[,] GenLargestCycle(int N) {

        var result = new bool[N, N];

        for (int i = 0; i < N-1; i++) {

            result[i, i + 1] = result[i + 1, i] = true;

        }

        result[0, N - 1] = result[N - 1, 0] = true;

        return result;

    }

}