Problem:


Score : 1400 points

Problem Statement

There are N turkeys.
We number them from 1 through N.

M men will visit here one by one.
The i-th man to visit will take the following action:

If both turkeys x_i and y_i are alive: selects one of them with equal probability, then eats it.

If either turkey x_i or y_i is alive (but not both): eats the alive one.

If neither turkey x_i nor y_i is alive: does nothing.

Find the number of pairs (i,\ j) (1 ≤ i < j ≤ N) such that the following condition is held:

The probability of both turkeys i and j being alive after all the men took actions, is greater than 0.

Constraints

2 ≤ N ≤ 400

1 ≤ M ≤ 10^5

1 ≤ x_i < y_i ≤ N

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the number of pairs (i,\ j) (1 ≤ i < j ≤ N) such that the condition is held.

Sample Input 1

3 1
1 2

Sample Output 1

2

(i,\ j) = (1,\ 3), (2,\ 3) satisfy the condition.

Sample Input 2

4 3
1 2
3 4
2 3

Sample Output 2

1

(i,\ j) = (1,\ 4) satisfies the condition.
Both turkeys 1 and 4 are alive if:

The first man eats turkey 2.

The second man eats turkey 3.

The third man does nothing.

Sample Input 3

3 2
1 2
1 2

Sample Output 3

0

Sample Input 4

10 10
8 9
2 8
4 6
4 9
7 8
2 8
1 8
3 4
3 4
2 7

Sample Output 4

5



Sample input:
3 1
1 2


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys

from itertools import combinations


def solve(n, pairs):
    survivors = {v: {v} for v in range(1, n + 1)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return sum(su.isdisjoint(sv) for su, sv in combinations(survivors.values(), 2))


n, m = map(int, input().split())
pairs = []
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    pairs.append((x, y))
print(solve(n, pairs))

Submission status: Time Limit Exceeded

Solution code:
import sys

from itertools import combinations


def solve(n, pairs):
    have_to_survive = [{v} for v in range(1, n + 1)]
    survivors = [True] * n
    for x, y in reversed(pairs):
        for i, srv in enumerate(survivors):
            if not srv:
                continue
            hts = have_to_survive[i]
            if x in hts:
                if y in hts:
                    survivors[i] = False
                else:
                    hts.add(y)
            elif y in hts:
                hts.add(x)

    finalists = [hts for srv, hts in zip(survivors, have_to_survive) if srv]
    return sum(su.isdisjoint(sv) for su, sv in combinations(finalists, 2))


n, m = map(int, input().split())
pairs = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
print(solve(n, pairs))

Submission status: Time Limit Exceeded

Solution code:
import sys

from itertools import combinations


def solve(n, pairs):
    def update(x, y):
        def f(srv):
            if x in srv:
                if y in srv:
                    return False
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
            return srv

        return f

    survivors = [{v} for v in range(1, n + 1)]
    for x, y in reversed(pairs):
        f = update(x, y)
        survivors = [srv for srv in survivors if f(srv)]
    return sum(su.isdisjoint(sv) for su, sv in combinations(survivors, 2))


n, m = map(int, input().split())
pairs = []
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    pairs.append((x, y))
print(solve(n, pairs))

Submission status: Time Limit Exceeded

Solution code:
import sys

from itertools import combinations

n, m = map(int, input().split())
survivors = {v: {v + 1} for v in range(n)}
for x, y in reversed(list(map(int, line.split()) for line in sys.stdin.readlines())):
    for v, srv in survivors.copy().items():
        if x in srv:
            if y in srv:
                del survivors[v]
            else:
                srv.add(y)
        elif y in srv:
            srv.add(x)
print(sum(su.isdisjoint(sv) for su, sv in combinations(survivors.values(), 2)))

Submission status: Time Limit Exceeded

Solution code:
import sys

from itertools import combinations


def solve(n, pairs):
    survivors = {v: {v + 1} for v in range(n)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return sum(su.isdisjoint(sv) for su, sv in combinations(survivors.values(), 2))


n, m = map(int, input().split())
pairs = []
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    pairs.append((x, y))
print(solve(n, pairs))

Submission status: Time Limit Exceeded

Solution code:
import sys

from itertools import combinations


def solve(n, pairs):
    survivors = {v: {v} for v in range(n)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return sum(su.isdisjoint(sv) for su, sv in combinations(survivors.values(), 2))


n, m = map(int, input().split())
pairs = []
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    pairs.append((x, y))
print(solve(n, pairs))

Submission status: Time Limit Exceeded

Solution code:
def get_survivors(n, pairs):
    survivors = {v: {v} for v in range(n)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return list(survivors.values())


def solve(n, pairs):
    survivors = get_survivors(n, pairs)
    ans = 0

    for i, su in enumerate(survivors):
        for sv in survivors[i + 1:]:
            if su.isdisjoint(sv):
                ans += 1
    return ans


n, m = map(int, input().split())
pairs = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    pairs.append((x, y))
print(solve(n, pairs))

Submission status: Time Limit Exceeded

Solution code:
def get_survivors(n, pairs):
    survivors = {v: {v} for v in range(n)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return survivors


def solve(n, pairs):
    survivors = get_survivors(n, pairs)
    ans = 0
    for u, su in survivors.items():
        for v, sv in survivors.items():
            if u >= v:
                continue
            if su.isdisjoint(sv):
                ans += 1
    return ans


n, m = map(int, input().split())
pairs = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    pairs.append((x, y))
print(solve(n, pairs))

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

N,M=map(int,input().split())
eat=[]
for i in range(M):
    x,y=map(int,input().split())
    eat.append((x,y))

eat=eat[::-1]

turkey=[]
for i in range(1,N+1):
    tempval=set([i])
    tempid=set([])
    for j in range(M):
        x,y=eat[j]
        if x in tempval and y in tempval:
            break
        elif x in tempval:
            tempval.add(y)
            tempid.add(j)
        elif y in tempval:
            tempval.add(x)
            tempid.add(j)
    else:
        turkey.append([tempval,tempid])

ans=0
n=len(turkey)
#print(turkey)
for i in range(1,n):
    for j in range(i):
        aval,aid=turkey[i]
        bval,bid=turkey[j]
        checkval=True
        checkid=True
        for val in bval:
            checkval=checkval&(val not in aval)
        for id in bid:
            checkid=checkid&(id not in aid)
        if checkid and checkval:
            ans+=1
            #print(i,j)

print(ans)

Submission status: Accepted

Solution code:
import sys

from itertools import combinations


def solve(n, pairs):
    survivors = {v: {v} for v in range(1, n + 1)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return sum(su.isdisjoint(sv) for su, sv in combinations(survivors.values(), 2))


n, m = map(int, input().split())
pairs = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
print(solve(n, pairs))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
v=[[1 for i in range(n)] for i in range(n)]
for i in range(m):	
	x,y=map(int,input().split())
	x-=1
	y-=1
	if v[x][y]:
		v[x][y],v[y][x]=0,0
		for j in range(n):
			if v[x][j]==0:
				v[j][y],v[y][j]=0,0
		for j in range(n):
			if v[y][j]==0:
				v[j][x],v[x][j]=0,0
	else:
		for j in range(n):
			v[j][x],v[x][j],v[j][y],v[y][j]=0,0,0,0
print((sum(map(sum,v))-sum([v[i][i] for i in range(n)]))//2)

Submission status: Runtime Error

Solution code:
import sys

from itertools import combinations

n, m = map(int, input().split())
survivors = {v: {v + 1} for v in range(n)}
for x, y in reversed(map(int, line.split()) for line in sys.stdin.readlines()):
    for v, srv in survivors.copy().items():
        if x in srv:
            if y in srv:
                del survivors[v]
            else:
                srv.add(y)
        elif y in srv:
            srv.add(x)
print(sum(su.isdisjoint(sv) for su, sv in combinations(survivors.values(), 2)))

Submission status: Runtime Error

Solution code:
def get_survivors(n, pairs):
    survivors = {v: {v} for v in range(n)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return survivors.values()


def solve(n, pairs):
    survivors = get_survivors(n, pairs)
    ans = 0

    for i, su in enumerate(survivors[:-1]):
        for sv in survivors[i + 1:]:
            if su.isdisjoint(sv):
                ans += 1
    return ans


n, m = map(int, input().split())
pairs = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    pairs.append((x, y))
print(solve(n, pairs))

Submission status: Runtime Error

Solution code:
def get_survivors(n, pairs):
    survivors = {v: {v} for v in range(n)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return survivors.values()


def solve(n, pairs):
    survivors = get_survivors(n, pairs)
    ans = 0

    for i, su in enumerate(survivors):
        for sv in survivors[i + 1:]:
            if su.isdisjoint(sv):
                ans += 1
    return ans


n, m = map(int, input().split())
pairs = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    pairs.append((x, y))
print(solve(n, pairs))