Problem:


Score : 700 points

Problem Statement

You are given an integer N.
Build an undirected graph with N vertices with indices 1 to N that satisfies the following two conditions:

The graph is simple and connected.

There exists an integer S such that, for every vertex, the sum of the indices of the vertices adjacent to that vertex is S.

It can be proved that at least one such graph exists under the constraints of this problem.

Constraints

All values in input are integers.

3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:

N

Output

In the first line, print the number of edges, M, in the graph you made. In the i-th of the following M lines, print two integers a_i and b_i, representing the endpoints of the i-th edge.

The output will be judged correct if the graph satisfies the conditions.

Sample Input 1

3

Sample Output 1

2
1 3
2 3

For every vertex, the sum of the indices of the vertices adjacent to that vertex is 3.



Sample input:
3


Sample output:
2
1 3
2 3

Submission status: Wrong Answer

Solution code:
n = int(input())
total = n * (n - 1) // 2
if n % 2 == 1:
  total -= (n - 1) // 2
  print(total)
  for i in range(1, n):
    for j in range(i + 1, n + 1):
      if i + j != n:
        print(i, j)
else:
  total -= n // 2 
  for i in range(1, n):
    for j in range(i + 1, n + 1):
      if i + j != n + 1:
        print(i, j)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
i=1
while(i<=n):
    j=i+1
    while(j<=n):
        if j!=n-i:
            a+=[(i,j)]
        j+=1
    i+=1
print(len(a))
for x in a:
    print(*x)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
i=1
while(i<=n):
    j=i+1
    while(j<=n):
        if j!=n-i:
            a+=[(i,j)]
        j+=1
    i+=1
for x in a:
    print(*x)

Submission status: Wrong Answer

Solution code:
N = int(input())

if N > 6:
    sumN = (N + N * N) // 2 // 3
    tmp = [[i for i in range(1, N // 3 + 1)], [i for i in range(N // 3 + 1, 2 * N // 3 + 1)],
           [i for i in range(2 * N // 3 + 1, N + 1)]]
    #print(tmp)
    group = [[], [], []]

    j = 0
    for i in tmp[0]:
        if j % 3 == 0:
            group[0].append(i)
        if j % 3 == 1:
            group[1].append(i)
        if j % 3 == 2:
            group[2].append(i)
        j += 1

    j = 0
    for i in tmp[1]:
        if j % 3 == 1:
            group[0].append(i)
        if j % 3 == 2:
            group[1].append(i)
        if j % 3 == 0:
            group[2].append(i)
        j += 1

    j = 0
    for i in tmp[2]:
        if j % 3 == 2:
            group[0].append(i)
        if j % 3 == 0:
            group[1].append(i)
        if j % 3 == 1:
            group[2].append(i)
        j += 1

    #print(group)
    ans = []
    for i in group[0]:
        for j in group[1]:
            ans.append([i, j])
        for j in group[2]:
            ans.append([i, j])

    for i in group[1]:
        for j in group[2]:
            ans.append([i, j])
    ans.sort()
    print(len(ans))
    for i in ans:
        print(i[0], i[1])

elif N == 3:
    print(2)
    print(1, 3)
    print(2, 3)
elif N == 6:
    ans = []
    group = [[1, 6], [2, 5], [3, 4]]
    for i in group[0]:
        for j in group[1]:
            ans.append([i, j])
        for j in group[2]:
            ans.append([i, j])

    for i in group[1]:
        for j in group[2]:
            ans.append([i, j])
    print(len(ans))
    for i in ans:
        print(i[0], i[1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict, Counter
from itertools import permutations, product, combinations
from bisect import bisect, bisect_left
from fractions import gcd
MOD = 10**9 + 7

def inpl(): return list(map(int, input().split()))

N = int(input())
searched = 0*[N+1]

if (N*(N+1)//2)%2 == 0:
    target = N*(N+1)//4
    A = []
    B = []
    for i in range(N, 0, -1):
        if i <= target:
            A.append(i)
            target -= i
    assert target == 0
    A = set(A)
    B = set(range(1, N+1)) - A

    print(len(A)*len(B))
    for a in A:
        for b in B:
            print(a, b)

else:
    target = N*(N+1)//6
    A = []
    B = []
    for i in range(N, 0, -1):
        if i <= target:
            A.append(i)
            target -= i
    assert target == 0
    A = set(A)

    target = N*(N+1)//6
    for i in range(N, 0, -1):
        if i <= target and not i in A:
            B.append(i)
            target -= i
    assert target == 0
    B = set(B)
    C = set(range(1, N+1)) - A - B
    
    print(len(A)*len(B) + len(B)*len(C) + len(C)*len(A))
    for X, Y in [[A, B], [B, C], [C, A]]:
        for x in X:
            for y in Y:
                print(x, y)

Submission status: Wrong Answer

Solution code:
N = int(input())

M = N - 1
print(M)
for n in range(N-2):
    print('%i %i' % (1, N))
print('%i %i' % (2, N))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = 0
for i in range(2, N):
    S += i

Ans = []

for i in range(2, N):
    Ans.append((1, i))
    Ans.append((N, i))
  

Total = [N+1] * N
Total[0], Total[N-1] = S, S
for i in range(1, N-1):
    j = i+1
    while Total[i] < S:
        Ans.append((i+1, j+1))
        Total[i] += j+1
        Total[j] += i+1
        j += 1
       

print(len(Ans))
for a in Ans:
    print(" ".join(map(str, a)))

Submission status: Wrong Answer

Solution code:
n=int(input())
print((n*(n-1))//2)
for i in range(1,n+1):
  for j in range(i+1,n+1):
    print(i,j)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n-1):
    for j in range(i+1,n):
        a.append([i+1,j+1])
for i in a:
    if n%2==1:
        if sum(i)!=n:
            print(i[0],i[1])
    else:
        if sum(i)!=n+1:
            print(i[0],i[1])

Submission status: Wrong Answer

Solution code:
n = int(input())

ans = []
ps = []
if n % 2 == 0:
    ps = [1, n]
    for i in range(2, n // 2 + 1):
        for p in ps:
            ans.append((i, p))
            ans.append((n + 1 - i, p))
        ps.append(i)
        ps.append(n + 1 - i)
else:
    ps = [1, n - 1, n]
    ans.append((1, n))
    ans.append((n - 1, n))
    for i in range(2, n // 2 + 1):
        for p in ps:
            ans.append((i, p))
            ans.append((n - i, p))
        ps.append(i)
        ps.append(n - i)
        print(ps)

print(len(ans))
print("\n".join([" ".join(map(str, ai)) for ai in ans]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N = II()
    ans = []
    if N % 2 == 1:
        for i in range(1, N):
            ans.append([N, i])
        for i in range(2, N - 1):
            ans.append([1, i])
            ans.append([N - 1, i])
    else:
        for i in range(1, N + 1):
            j = (N + 1) - i
            for k in range(1, i):
                if k not in (i, j):
                    ans.append([i, k])
    print(len(ans))
    for x in ans:
        print(*x)

    return 0

main()

Submission status: Wrong Answer

Solution code:
n = int(input())

print(n-1)

for i in range(1, n):
    if(i == 1 or i == n-1):
        print(i, n)
    else:
        print(i, i+1)

Submission status: Wrong Answer

Solution code:
n = int(input())

if n%2 == 0:
    su = n+1
    print((n*(n-1)//2)-n//2)
    for i in range(1,n+1):
        for k in range(1,n+1):
            if i+k != su and i < k:
                print(i,k)
if n%2 == 1:
    su = n+1
    print((n*(n-1)//2)-(n-1)//2)
    for i in range(1,n+1):
        for k in range(1,n+1):
            if i+k != su and i < k:
                print(i,k)

Submission status: Wrong Answer

Solution code:
N = int(input())
list_ = [x for x in range(N)]

if N%2 == 0:
  cmb_list = [[k, N-k+1] for k in range(1,int(N/2)+1)]
else:
  cmb_list = [[k, N-k] for k in range(1,int(N/2+1))]
  cmb_list.append([N])

for list_ in cmb_list:
  for c in list_:
    for idx in range(1,c):
      if (idx not in list_):
        print("%s %s"%(idx, c))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N = II()
    if N % 2 == 1:
        for i in range(1, N):
            print(N, i)
        for i in range(2, N - 1):
            print(1, i)
            print(N - 1, i)
    else:
        for i in range(1, N + 1):
            j = (N + 1) - i
            for k in range(1, i):
                if k not in (i, j):
                    print(i, k)

    return 0

main()

Submission status: Wrong Answer

Solution code:
n = input().strip()
n = int(n)
r = set()
if n % 2 == 0:
    x = n + 1
    for i in range(n):
        i = i + 1
        for j in range(n):
            j = j + 1
            if j <= i:
                continue
            if i + j == x:
                continue
            print(i,j)
else:
    m = n - 1
    x = n
    for i in range(m):
        i = i + 1
        for j in range(m):
            j = j + 1
            if j <= i:
                continue
            if i + j == x:
                continue
            print(i,j)
    for i in range(m):
        print(i+1, x)

Submission status: Wrong Answer

Solution code:
#import collections as c
#ip = lambda : map(int, input().split())

#################
N = int(input())
S = N*(N+1)/2
a = []
b = []

f = 1
for i in range(N,0,-1):
    if f%4==1 or f%4==0:
        a.append(i)
        f += 1
    else:
        b.append(i)
        f += 1
print(len(a)*len(b))
for ia in a:
    for ib in b:
        print(ia,ib)

Submission status: Wrong Answer

Solution code:
n = int(input())
print(n*(n-1)//2-n//2)
for i in range(1,n):
  for j in range(i+1,n+1):
    if i == j or i+j == n+1:
      continue
    print(i,j)

Submission status: Wrong Answer

Solution code:
#import collections as c
#ip = lambda : map(int, input().split())

#################
N = int(input())
S = N*(N+1)/2
r = []
a = []
b = []

f = 1
for i in range(N,0,-1):
    if f%4==1 or f%4==0:
        a.append(i)
        f += 1
    else:
        b.append(i)
        f += 1
for ia in a:
    for ib in b:
        print(ia,ib)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from functools import reduce


class Divisor:
    def __init__(self, n):
        """ make divisors list and prime factorization list of n
            complexity: O(n^(1/2))
            used in ProjectEuler No.12, yukicoder No.36
        """
        assert(n >= 1)
        number = n
        if number == 1:
            self.primeFactorization = {1: 1}
        else:
            self.primeFactorization = {}
            for i in range(2, int(n**0.5)+1):
                cnt = 0
                while number % i == 0:
                    cnt += 1
                    number //= i
                if cnt > 0:
                    self.primeFactorization[i] = cnt
            if number > 1:
                self.primeFactorization[number] = 1

    def primeFactors(self):
        return deepcopy(self.primeFactorization)

    def numDivisors(self):
        """ the number of divisors """
        if self.primeFactorization.get(1, 0) == 1:
            return 1
        numDiv = 1
        for _, cnt in self.primeFactorization.items():
            numDiv *= cnt+1
        return numDiv

    def sumDivisors(self):
        return reduce(lambda x, y: x * y, [sum(p**i for i in range(n+1)) for p, n in self.primeFactorization.items()])


def divisorsList(n):
    assert(n >= 1)
    divsList = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divsList.append(i)
            if n // i != i:
                divsList.append(n//i)
    return sorted(divsList)


def subsum(arr, M):
    dp = [0] * (M + 1)
    prev = [-1] * (M + 1)
    dp[0] = 1
    for x in arr:
        for i in reversed(range(M + 1)):
            if dp[i] and i + x <= M:
                dp[i + x] = 1
                prev[i + x] = i
    assert dp[-1]
    ans = []
    now = M
    while prev[now] != -1:
        ans.append(now - prev[now])
        now = prev[now]
    return ans


def dfs(groups, i, now):
    if i == len(groups):
        print(*now)
        return
    for x in groups[i]:
        now.append(x)
        dfs(groups, i + 1, now)
        now.pop()


def main(N):
    sumall = N * (N + 1) // 2
    group_num = divisorsList(sumall)[1]
    groups = []
    selected = set()
    rest = list(range(1, N + 1))
    for i in range(group_num):
        g = subsum(rest, sumall // group_num)
        groups.append(g)
        selected |= set(g)
        rest = [x for x in rest if x not in selected]
    edges = []
    for i in range(len(groups)):
        for j in range(len(groups)):
            if i >= j:
                continue
            for x1 in groups[i]:
                for x2 in groups[j]:
                    edges.append((x1, x2))
    print(len(edges))
    for e in edges:
        print(*e)





if __name__ == '__main__':
    N = int(input())
    main(N)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n = ni()

a = [i for i in range(1,101)]
acc = list(accumulate(a))

if n%2:
    groups = [[i, n-i] for i in range(1,(n+1)//2)]
    groups.append([n])
else:
    groups = [[i, n-i] for i in range(1,(n+1)//2)]
    
edges = []

for i in range(len(groups)):
    for j in range(len(groups[i])):
        for k in range(1,n+1):
            if k in groups[i] or groups[i][j] > k:
                continue
            
            else:
                edges.append([groups[i][j], k])
                
print(len(edges))
for ei in edges:
    print(*ei)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==3:
	print(1,3)
	print(2,3)
else:
	for i in range(1,n+1):
		print(i,end=" ")
		for j in range(1,n+1):
			if j!=i and j+i!=n+1:
				print(j,end=" ")
		print()

Submission status: Wrong Answer

Solution code:
def balanced_neighbors(N: int)->list:
    if N < 3:
        return []

    return balanced_neighbors(N-1) + [(i, N) for i in range(1, N)]


if __name__ == "__main__":
    N = int(input())
    ans = balanced_neighbors(N)

    print(len(ans))
    for a, b in ans:
        print(a, b)

Submission status: Wrong Answer

Solution code:
def solve():
  N = int(input())
  M = (N - 2) * 2
  for i in range(3, N + 1):
    print('1 {0}\n{1} {0}'.format(i, i - 1))

solve()

Submission status: Wrong Answer

Solution code:
n=int(input())
if(n%2!=0):
  print(n-1)
  for i in range(1,n):
    print(i,i+1)
else:
  print(n)
  for i in range(1,n):
    print(i,i+1)
  print(n,1)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = []
for i in range(1, n + 1):
    for j in range(i, n + 1):
        if i != j and i + j != n + 1:
            lst.append((i, j))

print(len(lst))
for s in lst:
    print(*s)

Submission status: Time Limit Exceeded

Solution code:
def g(i, left):
    if left <= 0: return None
    ret = set()
    for j in range(i, n+1):
        r = g(j+1, left)
        if r: ret |= r
        r = g(j+1, left-j)
        if r: ret |= set((j,) + x for x in r)
        if j == left: ret |= {(j,),}
    return ret

def f(s, i, d):
    left = s - sum(d.get(i, [0]))
    if left < 0: return None
    if left == 0: return d
    for j in g(i, left):
        e = dict(d)
        for k in j:
            e.setdefault(k, []).append(i)
        r = f(s, i+1, e)
        if r: return r
    return None

n = int(input())
n = 100
for i in range(100):
    s = n + i
    r = f(s, 1, {})
    if r:
        print(sum(len(x) for x in r.values()))
        for k,v in r.items():
            for x in v:
                print(k, x)
        break

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def addEdge(a,b,adjacent):
    adjacent[a][b] += 1
    adjacent[b][a] += 1

def checkSum(adjacent):
    N = len(adjacent)
    sumList = np.zeros((N), dtype = int)

    for i in range(N):
        for j in range(N):
            if (i < j):
                if(adjacent[i][j] == 1): sumList[i] += j + 1
                if(adjacent[j][i] == 1): sumList[j] += i + 1
    isSameSum = all(sumList[0] == sumList)
    # if(isSameSum) :
    #     print(sumList)
    return isSameSum

def isSeparate(adjacent):
    degree = sum(adjacent)
    # print("degree = " + str(degree))
    return any(degree == 0)

def visit(v, yet, adjacent):
    yet[v] = 0
    for w in range(len(adjacent)):
        if adjacent[v][w] == 1 and yet[w] == 1:
            visit(w, yet, adjacent)

def connectCheck(adjacent):
    yetToVisit = []
    count = 0
    for i in range(len(adjacent)):
        yetToVisit.append(1)

    for i in range(len(adjacent)):
        if yetToVisit[i] == 1:
            count += 1
        visit(i, yetToVisit, adjacent)
    return count

N = int(input())

edgeNum = int((N-1)*N / 2)
# print(edgeNum)
edge = np.zeros((edgeNum, 2), dtype = int)
ei = 0
for i in range(N):
    for j in range(N):
        if(i < j):
            edge[ei][0] = i
            edge[ei][1] = j
            ei += 1

# print(edge)

# adjacent = np.zeros((N, N), dtype = int)
# addEdge(1,2,adjacent)

for count in range(2**edgeNum):
    #print("count = "+ str(count))
    c = count
    adjacent = np.zeros((N, N), dtype = int)

    for i in range(edgeNum-1, -1, -1):
        if(c >= (2 ** i)):
            c -= 2 ** i
            a = edge[i][0]
            b = edge[i][1]
            adjacent[a][b] += 1
            adjacent[b][a] += 1

    if(connectCheck(adjacent) == 1):
        if(checkSum(adjacent)):
            # checkSum(adjacent)
            # print("count = " + str(count))
            # print(adjacent)

            # 辺の本数の出力
            print(int(sum(sum(adjacent))/2))

            # 辺の内容の出力
            for i in range(N):
                for j in range(N):
                    if(i < j):
                        if(adjacent[i][j] != 0):
                            print(str(i+1) + " " + str(j+1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def addEdge(a, b, adjacent):
    adjacent[a][b] += 1
    adjacent[b][a] += 1

def checkSum(adjacent):
    N = len(adjacent)
    sumList = np.zeros((N), dtype=int)

    for i in range(N):
        for j in range(N):
            if (i < j):
                if (adjacent[i][j] == 1): sumList[i] += j + 1
                if (adjacent[j][i] == 1): sumList[j] += i + 1
    isSameSum = all(sumList[0] == sumList)
    # if(isSameSum) :
    # print(sumList)
    return isSameSum


def visit(v, yet, adjacent):
    yet[v] = 0
    for w in range(len(adjacent)):
        if adjacent[v][w] == 1 and yet[w] == 1:
            visit(w, yet, adjacent)


def connectCheck(adjacent):
    yetToVisit = []
    count = 0
    for i in range(len(adjacent)):
        yetToVisit.append(1)

    for i in range(len(adjacent)):
        if yetToVisit[i] == 1:
            count += 1
        visit(i, yetToVisit, adjacent)
    return count


N = int(input())

edgeNum = int((N - 1) * N / 2)
# print(edgeNum)
edge = np.zeros((edgeNum, 2), dtype=int)
ei = 0
for i in range(N):
    for j in range(N):
        if (i < j):
            edge[ei][0] = i
            edge[ei][1] = j
            ei += 1

# print(edge)

# adjacent = np.zeros((N, N), dtype = int)
# addEdge(1,2,adjacent)

for count in range(2 ** edgeNum):
    # print("count = "+ str(count))
    c = count
    adjacent = np.zeros((N, N), dtype=int)

    for i in range(edgeNum - 1, -1, -1):
        if (c >= (2 ** i)):
            c -= 2 ** i
            a = edge[i][0]
            b = edge[i][1]
            adjacent[a][b] += 1
            adjacent[b][a] += 1

    if (checkSum(adjacent)):
        if (connectCheck(adjacent) == 1):
            # checkSum(adjacent)
            # print("count = " + str(count))
            # print(adjacent)

            # 辺の本数の出力
            print(int(sum(sum(adjacent)) / 2))

            # 辺の内容の出力
            for i in range(N):
                for j in range(N):
                    if (i < j):
                        if (adjacent[i][j] != 0):
                            print(str(i + 1) + " " + str(j + 1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def addEdge(a, b, adjacent):
    adjacent[a][b] += 1
    adjacent[b][a] += 1

def checkSum(adjacent):
    N = len(adjacent)
    sumList = np.zeros((N), dtype=int)

    for i in range(N):
        for j in range(N):
            if (i < j):
                if (adjacent[i][j] == 1): sumList[i] += j + 1
                if (adjacent[j][i] == 1): sumList[j] += i + 1
    isSameSum = all(sumList[0] == sumList)
    # if(isSameSum) :
    # print(sumList)
    return isSameSum


def visit(v, yet, adjacent):
    yet[v] = 0
    for w in range(len(adjacent)):
        if adjacent[v][w] == 1 and yet[w] == 1:
            visit(w, yet, adjacent)


def connectCheck(adjacent):
    yetToVisit = []
    count = 0
    for i in range(len(adjacent)):
        yetToVisit.append(1)

    for i in range(len(adjacent)):
        if yetToVisit[i] == 1:
            count += 1
        visit(i, yetToVisit, adjacent)
    return count


N = int(input())

edgeNum = int((N - 1) * N / 2)
# print(edgeNum)
edge = np.zeros((edgeNum, 2), dtype=int)
ei = 0
for i in range(N):
    for j in range(N):
        if (i < j):
            edge[ei][0] = i
            edge[ei][1] = j
            ei += 1

# print(edge)

# adjacent = np.zeros((N, N), dtype = int)
# addEdge(1,2,adjacent)

for count in range(2 ** edgeNum):
    # print("count = "+ str(count))
    c = count
    adjacent = np.zeros((N, N), dtype=int)

    for i in range(edgeNum - 1, -1, -1):
        if (c >= (2 ** i)):
            c -= 2 ** i
            a = edge[i][0]
            b = edge[i][1]
            adjacent[a][b] += 1
            adjacent[b][a] += 1

    if (connectCheck(adjacent) == 1):
        if (checkSum(adjacent)):
            # checkSum(adjacent)
            # print("count = " + str(count))
            # print(adjacent)

            # 辺の本数の出力
            print(int(sum(sum(adjacent)) / 2))

            # 辺の内容の出力
            for i in range(N):
                for j in range(N):
                    if (i < j):
                        if (adjacent[i][j] != 0):
                            print(str(i + 1) + " " + str(j + 1))

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())

originLinks = list(itertools.combinations(list(range(1,n+1)), 2))
originLinkNum = len(originLinks)
end = False
for leftLinkNum in range(1, originLinkNum):
  # print(leftLinkNum)
  if end:
    break
  tempGraph = list(itertools.combinations(originLinks, leftLinkNum))
  # print(tempGraph)
  for graph in tempGraph:
    # print(graph)
    sums = [0] * n
    for link in graph:
      sums[link[0]-1] += link[1]
      sums[link[1]-1] += link[0]
    # print(sums, len(set(sums)))
    if len(set(sums)) == 1:
      #print(graph)
      print(len(graph))
      for link in graph:
        print(" ".join(list(map(str, link))))
      end = True
      break

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())

originLinks = list(itertools.combinations(list(range(1,n+1)), 2))
originLinkNum = len(originLinks)
end = False
for lostLinkNum in range(1, originLinkNum):
  if end:
    break
  tempGraph = itertools.combinations(originLinks, originLinkNum - lostLinkNum)
  for graph in tempGraph:
    #print(graph)
    sums = [0] * n
    for link in graph:
      sums[link[0]-1] += link[1]
      sums[link[1]-1] += link[0]
    if len(set(sums)) == 1:
      #print(graph)
      print(len(graph))
      for link in graph:
        print(" ".join(list(map(str, link))))
      end = True
      break

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  ans=set()
  if n%2==0:
    for i in range(n):
      for j in range(i+1,n):
        if i==j:
          continue
        if n+1==(i+1)+(j+1):
          continue
        ans.add((i+1,j+1))
  else:
    for i in range(n):
      for j in range(i+1,n):
        if i==j:
          continue
        if n==(i+1)+(j+1):
          continue
        ans.add((i+1,j+1))
  print(len(ans))
  for x,y in ans:
    print(x,y)

main()
# print(main())

Submission status: Accepted

Solution code:
N = int(input())
print(N*(N-1)//2 - N//2)
if(N%2 == 0):
    for i in range(1,N):
        for j in range(i+1,N+1):
            if(i+j != N+1):
                print(*[i,j])
else:
    for i in range(1,N):
        for j in range(i+1,N+1):
            if(i+j != N):
                print(*[i,j])

Submission status: Accepted

Solution code:
n=int(input())
ans=[]
s=n+1-n%2
for i in range(1,n+1-n%2):
  for j in range(i+1,n+1-n%2):
    if i+j==s:
      continue
    ans.append(str(i)+" "+str(j))
if n%2:
  for i in range(1,n):
    ans.append(str(i)+" "+str(n))
print(len(ans))
print("\n".join(ans))

Submission status: Accepted

Solution code:
n=int(input())

if n%2==0:
    m=n*(n-1)//2-n//2
    print(m)
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            if i+j==n+1:
                continue
            print('{} {}'.format(i,j))
else:
    m=n*(n-1)//2-(n-1)//2
    print(m)
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            if i+j==n:
                continue
            print('{} {}'.format(i,j))

Submission status: Accepted

Solution code:
n = int(input())
l = []
if n%2:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j == n:
                continue
            l.append([i,j])
else:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j == n+1:
                continue
            l.append([i,j])
print(len(l))
for i in l:
    print(*i)

Submission status: Accepted

Solution code:
n = int(input())

num = n + (n % 2 == 0)
cnt, ans = 0, []
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if i + j != num:
            cnt += 1
            ans.append((i, j))

print(cnt)
for i, j in ans:
    print(i, j)

Submission status: Accepted

Solution code:
N=int(input())
P=N if N%2 else N+1
print(N*(N-1)//2-N//2)
for i in range(1,N+1):
    for j in range(1,i):
        if i+j==P:
            continue
        print(i,j)

Submission status: Accepted

Solution code:
N=int(input())

if N%2:
    print(N*(N-1)//2-N//2)
    for i in range(1,N+1):
        for j in range(1,i):
            if i+j==N:
                continue
            print(i,j)
else:
    print(N*(N-1)//2-N//2)
    for i in range(1,N+1):
        for j in range(1,i):
            if i+j==N+1:
                continue
            print(i,j)

Submission status: Accepted

Solution code:
def main():
    import itertools
    n = int(input())
    if n%2==0:
        rm = n+1
    else:
        rm = n
    ans = []
    for t in itertools.combinations((i+1 for i in range(n)), 2):
        if sum(t)!=rm:
            ans.append(t)
    print(len(ans))
    for a in ans:
        print(a[0],a[1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
bad = N if N % 2 else N + 1
ans = []
for i in range(1, N):
    for j in range(i + 1, N + 1):
        if i + j == bad:
            continue
        ans.append((i, j))
print(len(ans))

for x, y in ans:
    print(x, y)

Submission status: Accepted

Solution code:
N = int(input())

print((((N-1)*N)//2) - N//2)


if N % 2 == 1:
  ban = N
else:
  ban = N + 1


for i in range(1,N):
  for j in range(i+1,N+1):
    if i + j != ban:
      print(i,j)

Submission status: Accepted

Solution code:
n=int(input())
m=n-n%2+1
d=[[i+j+2!=m and i!=j for i in range(n)] for j in range(n)]
print(sum([sum(i) for i in d])//2)
for i in range(n):
  for j in range(i+1,n):
    if d[i][j]:print(i+1,j+1)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = []
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if i == j or i + j == n + (n + 1) % 2:
                continue
            ans.append([i, j])
    print(len(ans))
    for a in ans:
        print(" ".join(map(str, a)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()

    # Nが偶数の場合、完全N//2-partiteグラフ
    # Nが奇数の場合、完全(N-1)//2-partiteグラフに全ての頂点と隣接している頂点Nを加えたもの
    ans = []

    def f(n):
        for i in range(1, n // 2 + 1):
            for j in range(1, n + 1):
                if j != i and j != n + 1 - i:
                    if j < i:
                        ans.append((j, i))
                    else:
                        ans.append((i, j))
                    if j < n + 1 - i:
                        ans.append((j, n + 1 - i))
                    else:
                        ans.append((n + 1 - i, j))

    if N % 2 == 0:
        f(N)
    else:
        if N >= 5:
            f(N - 1)
        for i in range(1, N):
            ans.append((i, N))

    ans = set(ans)
    print(len(ans))
    for i, j in ans:
        print(i, j)
        
if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def agc032_b():
    n = int(input())
    g = [[1]*n for _ in range(n)]
    for i in range(n//2):
        j = 2*(n//2)-1-i
        g[i][j] = 0
        g[j][i] = 0
    cnt = (sum([sum(row) for row in g]) - n) // 2
    print(cnt)
    for i in range(n):
        for j in range(i+1, n):
            if g[i][j]: print('{} {}'.format(i+1, j+1))

if __name__ == '__main__':
    agc032_b()

Submission status: Accepted

Solution code:
n=int(input())

#Sはn以上になる
#単純グラフのため、末端は一つとしか接続しない点がでてくる
#つまりsはn以下
#Sはnとしてよい

tree=[[] for _ in range(n)]

for i in range(n):
    for j in range(n):
        if i!=j:
            tree[i].append(j)

ans=[]
if n%2==0:
    for i in range(n):
        for item in tree[i]:
            if item+1!=n-i:
                if i>item:
                    ans.append([i+1,item+1])

else:
    for i in range(n):
        if i==n-1:
            for item in tree[i]:
                if i>item:
                    ans.append([i+1,item+1])
        else:
            for item in tree[i]:
                if item+1!=n-(i+1):
                    if i>item:
                        ans.append([i+1,item+1])

print(len(ans))
for item in ans:
    print(item[0],item[1])