How to find minimum number of days for a schedule according to a preference via graph?

Hi everyone. I am tasked with a question as follows:

We have n players and we want to hold a wrestling tournament with exactly n * (n - 1) / 2 matches. In each day a player can only play at most one match. However, each player has a certain preference when it comes to playing others. Here is an input example:

4
4 2 3
3 4 1
2 4 1
1 2 3

In this example player 1 wants to play against 4 2 3 in order. This means that they want to play against player 4 before they play against 2 and so on. I am supposed to find a graph based solution which prints out the least number of days it takes to plan such a tournament or print -1 if it cannot be done.

My solution has been to create a preference queue for each player. Then for each day build a preference graph where edge (u, v) exists if and only if v is the front of the preference queue of edge u. Then I use DFS to extract all cycles of length 2. These cycles represent two players who are willing to play each other and I add the pair to a linked list called 'match'. Then I dequeue the preference queue's of said pair and continue to do so until either everyone plays against the players' they want to play against or we reach an impossible solution where no two players want to play against each other, in said case such schedule is impossible. The worst case running of this algorithm is Θ(n^3) and its best case is Θ(n^2) which unfortunately causes time limits when submitting so either the algorithm itself is not the best or it could be implemented better.

Here is the solution in python:

from typing import Optional
from collections import deque


class SinglyListNode:
    def __init__(self, key):
        self.key = key
        self.next: Optional["SinglyListNode"] = None

class SinglyLinkedList:
    
    def __init__(self):
        self.head: Optional[SinglyListNode] = None
    
    def listPrepend(self, key):
        node = SinglyListNode(key)
        node.next = self.head
        self.head = node
    
    def listDelete(self, node: SinglyListNode):
        if node == self.head:
            self.head = node.next
        else:
            prev = self.head
            while prev is not None and prev.next != node:
                prev = prev.next
            prev.next = node.next
    
    def listSearch(self, key):
        x = self.head
        while x is not None and x.key != key:
            x = x.next
        return x

class Vertex:
    
    def __init__(self, number: int):
        self.number = number
        self.color = None
        self.parent = None
        self.d = None
        self.f = None


class DirectedGraph:
    
    def __init__(self, n: int):
        self.V = [Vertex(i) for i in range(n)]
        self.E_n = 0
        self.Adj = [SinglyLinkedList() for _ in range(n)]
        # match is a linked list which stores cycles of length 2
        self.match = SinglyLinkedList()
        self.time = 0
    
    def addEdge(self, u: Vertex, v: Vertex):
        self.Adj[u.number].listPrepend(v)
        self.E_n += 1
    
    def removeEdge(self, u: Vertex, v: Vertex):
        node = self.Adj[u.number].listSearch(v)
        self.Adj[u.number].listDelete(node)
        self.E_n -= 1
    
    def isEmpty(self) -> bool:
        return self.E_n == 0

    def DFS(self):
        for u in self.V:
            u.color = 'W'
            u.parent = None
        self.time = 0
        self.match.head = None
        for u in self.V:
            if u.color == 'W':
                self.DFS_VISIT(u)
    
    def DFS_VISIT(self, u: Vertex):
        self.time += 1
        u.d = self.time
        u.color = 'G'
        x = self.Adj[u.number].head
        while x is not None:
            v = x.key
            if v.color == 'W':
                v.parent = u
                self.DFS_VISIT(v)
            elif v.color == 'G':
                # A cycle is now detected. Check if it is of length 2
                # meaning that two players want to play against each other
                # If yes, add the pair (v, u) to `match`.
                cycle_len = u.d - v.d + 1
                if cycle_len == 2:
                    self.match.listPrepend((v, u))
            x = x.next
        self.time += 1
        u.f = self.time
        u.color = 'B'

def wrestlingTournament(n: int, pref):
    G = DirectedGraph(n)
    # `P_Q` is an array of queue's storing each player's preferences
    P_Q = [deque() for i in range(n)]
    for (i, i_pref) in enumerate(pref):
        for j in i_pref:
            P_Q[i].append(G.V[j])
    for i in range(n):
        if len(P_Q[i]) > 0:
            G.addEdge(G.V[i], P_Q[i][0])
    G.DFS()
    # the loop ends only when all matches are covered (the graph is empty)
    # or when there is no viable schedule
    days = 0
    while not G.isEmpty() and G.match.head != None:
        days += 1
        x = G.match.head
        # `match` is a linked list which stores pairs of vertices
        # that create a cycle of length 2
        while x is not None:
            (u, v) = x.key
            P_Q[u.number].popleft()
            G.removeEdge(u, v)
            P_Q[v.number].popleft()
            G.removeEdge(v, u)
            if len(P_Q[u.number]) > 0:
                G.addEdge(u, P_Q[u.number][0])
            if len(P_Q[v.number]) > 0:
                G.addEdge(v, P_Q[v.number][0])
            x = x.next
        G.DFS()
    if G.isEmpty():
        return days
    else:
        return -1


if __name__ == "__main__":
    n = int(input())
    pref = [
        [int(x) - 1 for x in input().split()]
        for _ in range(n)
    ]
    print(wrestlingTournament(n, pref))

Our TA says that there is a solution which always runs in Θ(n^2) and that we must utilize topological sort. However, I cannot see how topological sort can help us here. If we use topological sort on each of the preference graphs then it's essentially the same as DFS. If we use it on the full graph where each vertex is connected to every other vertex, I don't see how that can help us either. I would like some help here as I have been stuck on this question for a while.

The question gives us the value of n on the first line. Then for the n following lines we will have n - 1 numbers representing the preference of each player. For instance, the given example given at the start is interpreted as:

n = 4
1: 4 > 2 > 3
2: 3 > 4 > 1
3: 2 > 4 > 1
4: 1 > 2 > 3

Remember, solutions must be graph based. The implementation is not really required and a detailed pseudocode will suffice.