이번 문제는 BFS를 통해 해결하였다. 서로 싫어하는 정보를 인접 행렬로 관리하였다. BFS를 통해 탐색을 하며 비교하는 둘의 인덱스에 해당하는 인접 행렬 값이 1이고, 아직 방문하지 않은 경우에 방문처리를 해주고, 결과 리스트에 현재의 팀과 다른 팀을 넣어주도록 하였다. 이 방법으로 답을 쉽게 구할 수 있었다.

Code

from collections import deque
n = int(input())
hater = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, n+1):
    tmp = list(map(int, input().split()))
    for j in range(1, len(tmp)):
        hater[i][tmp[j]] = 1
        hater[tmp[j]][i] = 1
visited = [False for _ in range(n+1)]
result = [0 for _ in range(n+1)]
def bfs(cur, t):
    q = deque()
    q.append((cur, t))
    visited[cur] = True
    result[cur] = t
    while q:
        cur, tm = q.popleft()
        for nxt in range(1, n+1):
            if hater[cur][nxt] == 1 and not visited[nxt]:
                visited[nxt] = True
                result[nxt] = -tm
                q.append((nxt, -tm))
for num in range(1, n+1):
    if not visited[num]:
        bfs(num, 1)
team = [[] for _ in range(2)]
for i in range(1, n+1):
    if result[i] == -1:
        team[0].append(i)
    elif result[i] == 1:
        team[1].append(i)
for i in range(2):
    print(len(team[i]))
    print(*team[i])