Party Organization (Codeforces 1600F)
Tags: Math, probabilities

On the great island of Baltia, there live $$$N$$$ people, numbered from $$$1$$$ to $$$N$$$. There are exactly $$$M$$$ pairs of people that are friends with each other. The people of Baltia want to organize a successful party, but they have very strict rules on what a party is and when the party is successful. On the island of Baltia, a party is a gathering of exactly $$$5$$$ people. The party is considered to be successful if either all the people at the party are friends with each other (so that they can all talk to each other without having to worry about talking to someone they are not friends with) or no two people at the party are friends with each other (so that everyone can just be on their phones without anyone else bothering them). Please help the people of Baltia organize a successful party or tell them that it's impossible to do so.

Input: The first line contains two integer numbers, $$$N$$$ ($$$5 \leq N \leq 2*10^5$$$) and $$$M$$$ ($$$0 \leq M \leq 2*10^5$$$) – the number of people that live in Baltia, and the number of friendships. The next $$$M$$$ lines each contains two integers $$$U_i$$$ and $$$V_i$$$ ($$$1 \leq U_i,V_i \leq N$$$) – meaning that person $$$U_i$$$ is friends with person $$$V_i$$$. Two friends can not be in the list of friends twice (no pairs are repeated) and a person can be friends with themselves ($$$U_i \ne V_i$$$).

Output: If it's possible to organize a successful party, print $$$5$$$ numbers indicating which $$$5$$$ people should be invited to the party. If it's not possible to organize a successful party, print $$$-1$$$ instead. If there are multiple successful parties possible, print any.


Sample Inputs:
6 3
1 4
4 2
5 4

5 4
1 2
2 3
3 4
4 5

Sample Outputs:
1 2 3 5 6

-1

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
_str = str
str = lambda x=b'': x if type(x) is bytes else _str(x).encode()
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict

def main():
    (n, m) = list(map(int, input().strip().split(' ')))
    adj = defaultdict(set)
    for _ in range(m):
        (u, v) = map(int, input().strip().split(' '))
        if u <= 48 and v <= 48:
            adj[u].add(v)
            adj[v].add(u)

    def check(a):
        num = 0
        for i in range(5):
            for j in range(i + 1, 5):
                num += a[j] in adj[a[i]]
        return num == 0 or num == 10
    n = min(n, 48) + 1
    for i1 in range(1, n):
        for i2 in range(i1 + 1, n):
            for i3 in range(i2 + 1, n):
                for i4 in range(i3 + 1, n):
                    for i5 in range(i4 + 1, n):
                        if check([i1, i2, i3, i4, i5]):
                            print(i1, i2, i3, i4, i5)
                            return
    print(-1)
    return
main()

Solution (Python):
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    (u, v) = map(int, input().split())
    u -= 1
    v -= 1
    if u >= 48 or v >= 48:
        continue
    G[u].append(v)
    G[v].append(u)
if n >= 48:
    G = G[:48]

def ok(a, b, c, d, e):
    allfd = True
    nofd = True
    people = [a, b, c, d, e]
    for x in people:
        for y in people:
            if x == y:
                continue
            if x in G[y]:
                nofd = False
            else:
                allfd = False
    return allfd or nofd
sz = len(G)
for a in range(sz):
    for b in range(a + 1, sz):
        for c in range(b + 1, sz):
            for d in range(c + 1, sz):
                for e in range(d + 1, sz):
                    if ok(a, b, c, d, e):
                        ans = [a, b, c, d, e]
                        print(*[x + 1 for x in ans])
                        exit()
print(-1)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def process(n, G):
    n = min(n, 1000)
    M = [[0 for j in range(n + 1)] for i in range(n + 1)]
    for (u, v) in G:
        if max(u, v) <= n:
            M[u][v] = 1
            M[v][u] = 1
    all_connect = []
    no_connect = []
    if M[1][2] == 1:
        all_connect.append([1, 2])
    else:
        no_connect.append([1, 2])
    for i in range(3, n + 1):
        new_all_connect = []
        new_no_connect = []
        for i2 in range(1, i):
            if M[i][i2] == 1:
                new_all_connect.append([i2, i])
            else:
                new_no_connect.append([i2, i])
        for x in all_connect:
            new_all_connect.append(x)
            works = True
            for y in x:
                if M[i][y] == 0:
                    works = False
                    break
            if works:
                if len(x + [i]) == 5:
                    return x + [i]
                new_all_connect.append(x + [i])
        for x in no_connect:
            new_no_connect.append(x)
            works = True
            for y in x:
                if M[i][y] == 1:
                    works = False
                    break
            if works:
                if len(x + [i]) == 5:
                    return x + [i]
                new_no_connect.append(x + [i])
        all_connect = new_all_connect
        no_connect = new_no_connect
    return [-1]
(n, m) = [int(x) for x in input().split()]
G = []
for i in range(m):
    (u, v) = [int(x) for x in input().split()]
    G.append([u, v])
answer = process(n, G)
sys.stdout.write(' '.join(map(str, answer)) + '\n')