Can We Split Into Two Teams?

Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Every person receives exactly one team; either team may be empty. People without a listed pair can go on either team. Check every connected group of constraints.

Implement split_into_two_teams(people, pairs).

Input

people: The number of people, numbered from 1.

pairs: Rows [first_person, second_person] that must be separated.

Output

Return true if any valid assignment exists, otherwise false. Do not return the assignment.

เงื่อนไข

1 ≤ people ≤ 100,000. 0…200,000 pairs of distinct person IDs in 1…people. Duplicate pairs are allowed and repeat the same constraint.

ตัวอย่าง

อินพุต:
pairs = [
    [1, 2],
    [2, 3],
    [3, 1]
]
people = 3

ผลลัพธ์ที่คาดหวัง:
expected = False

อินพุต:
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3},
    {3, 1}
};
long long people = 3;

ผลลัพธ์ที่คาดหวัง:
bool expected = false;

อินพุต:
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 1}
};
long people = 3;

ผลลัพธ์ที่คาดหวัง:
bool expected = false;

อินพุต:
pairs = [
    [1, 2],
    [2, 3]
]
people = 4

ผลลัพธ์ที่คาดหวัง:
expected = True

อินพุต:
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3}
};
long long people = 4;

ผลลัพธ์ที่คาดหวัง:
bool expected = true;

อินพุต:
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3}
};
long people = 4;

ผลลัพธ์ที่คาดหวัง:
bool expected = true;

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

• CSES: Building Teams