Vasya's older brother, Petya, attends an algorithm course in his school. Today he learned about matchings in graphs. Formally, a set of edges in a graph is called a matching if no pair of distinct edges in the set shares a common endpoint.
Petya instantly came up with an inverse concept, an antimatching. In an antimatching, any pair of distinct edges should have a common endpoint.
Petya knows that finding a largest matching in a graph is a somewhat formidable task. He wonders if finding the largest antimatching is any easier. Help him find the number of edges in a largest antimatching in a given graph.

-----Input:-----
The first line contains T$T$, number of test cases per file.
The first line of each test case contains two integers n$n$ and m−$m-$ the number of vertices and edges of the graph respectively (1≤n≤104$1 \leq n \leq 10^4$, 0≤m≤104$0 \leq m \leq 10^4$).
The next m$m$ lines describe the edges. The i$i$-th of these lines contains two integers ui$u_i$ and vi−$v_i-$ the indices of endpoints of the i$i$-th edge (1≤ui,vi≤n$1 \leq u_i, v_i \leq n$, ui≠vi$u_i \neq v_i$).
It is guaranteed that the graph does not contain self-loops nor multiple edges. It is not guaranteed that the graph is connected.

-----Output:-----
Print a single number per test case −$-$ the maximum size of an antichain in the graph.

-----Constraints-----
- 1≤T≤10$1 \leq T \leq 10$
- 1≤n≤104$1 \leq n \leq 10^4$
- 0≤m≤104$0 \leq m \leq 10^4$
- 1≤ui,vi≤n$1 \leq u_i, v_i \leq n$
- ui≠vi$u_i \neq v_i$

-----Sample Input:-----
3
3 3
1 2
1 3
2 3
4 2
1 2
3 4
5 0

-----Sample Output:-----
3
1
0

-----EXPLANATION:-----
In the first sample all three edges form an antimatching.
In the second sample at most one of the two edges can be included in an antimatching since they do not share common endpoints.
In the third sample there are no edges, hence the answer is 0$0$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Constructive algorithms


Solutions:
import sys
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for _ in range(m):
		(src, dest) = map(int, input().split())
		adj[src].append(dest)
		adj[dest].append(src)
	print(max(max([len(a) for a in adj]), 3 if any((not set(adj[x]).isdisjoint(adj[y]) for x in range(len(adj)) for y in adj[x])) else max([len(a) for a in adj])))


def snek(a):
	for x in range(len(a)):
		for y in a[x]:
			if not set(a[x]).isdisjoint(g[y]):
				return True
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	g = [[] for x in range(n)]
	for j in range(m):
		(u, v) = map(int, input().split())
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	h = []
	for k in range(len(g)):
		h.append(len(g[k]))
	h1 = max(h)
	if h1 >= 3:
		print(h1)
		continue
	if snek(g):
		print(3)
		continue
	print(h1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	L = [[] for i in range(n)]
	for i in range(m):
		(a, b) = map(int, input().split())
		L[a - 1].append(b - 1)
		L[b - 1].append(a - 1)
	l = 0
	for i in range(n):
		l = max(len(L[i]), l)
	if l >= 3:
		print(l)
		continue
	found1 = False
	for i in range(n):
		found2 = False
		for y in L[i]:
			s = set(L[i]).intersection(set(L[y]))
			if len(s) >= 1:
				found2 = True
				break
		if found2:
			found1 = True
			break
	if found1:
		print(3)
	else:
		print(l)


def detect_triangle(adj):
	for x in range(len(adj)):
		for y in adj[x]:
			if not set(adj[x]).isdisjoint(adj[y]):
				return True
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split())
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	h = []
	for i in range(len(graph)):
		h.append(len(graph[i]))
	h1 = max(h)
	if h1 >= 3:
		print(h1)
		continue
	if detect_triangle(graph):
		print(3)
		continue
	print(h1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	[adj[int(src)].append(int(dest)) or adj[int(dest)].append(int(src)) for _ in range(m) for (src, dest) in [map(int, input().split())]]
	print(max(max(map(len, adj)), 0 if max(map(len, adj)) > 2 else 3 if any((not set(adj[x]).isdisjoint(adj[y]) for x in range(n + 1) for y in adj[x])) else 0))


def get():
	return [int(x) for x in input().split()]
import sys

def detectTriangle(adj):
	for x in range(len(adj)):
		for y in adj[x]:
			if not set(adj[x]).isdisjoint(adj[y]):
				return True
for _ in range(int(input())):
	(n, m) = get()
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(src, dest) = get()
		src -= 1
		dest -= 1
		adj[src].append(dest)
		adj[dest].append(src)
	max_degree = max([len(a) for a in adj])
	if max_degree >= 3:
		print(max_degree)
		continue
	if detectTriangle(adj):
		print(3)
		continue
	print(max_degree)


def does_3_cycle_exist_in_the_graph(adjacency_list, n):
	for i in range(1, n + 1):
		if len(adjacency_list[i]) == 2 and adjacency_list[i][0] in adjacency_list[adjacency_list[i][1]]:
			return True
	return False
T = int(input())
while T:
	(n, m) = list(map(int, input().split()))
	adjacency_list = [[] for _ in range(n + 1)]
	while m:
		(u, v) = list(map(int, input().split()))
		adjacency_list[u].append(v)
		adjacency_list[v].append(u)
		m -= 1
	max_antimatching = 0
	for i in range(1, n + 1):
		max_antimatching = max(max_antimatching, len(adjacency_list[i]))
	if max_antimatching >= 3:
		print(max_antimatching)
	else:
		if does_3_cycle_exist_in_the_graph(adjacency_list, n) == True:
			max_antimatching = 3
		print(max_antimatching)
	T -= 1